2018西安电子科技大学第十六届“华为杯”大学生程序设计竞赛现场赛部分题解

2019-04-13 20:35发布

站内文章 / 模拟电子
16216 0 1202
总体来说，这次校赛打的中规中矩，算是正常发挥吧。过了4题，依靠罚时取得了还不错的成绩。下面发出一些题的题解（有的参考了其他人的思路）题目链接：https://www.nowcoder.com/acm/contest/107#question
--------------------------------------------------------------------------------------------------------------------------------A题大水题，就不啰嗦了，直接上代码#include #include using namespace std; char word[25]; int main() { int t; scanf("%d",&t); for(int i=0;iB题直接暴力找就可以了，复杂度O（mn）
#include #include #include #include #include #include #include #include using namespace std; char zimu[110]; char dian[1010][20]; int flag[30]; int main() { int n; while(scanf("%s",zimu)!=EOF) { memset(flag,0,sizeof(flag)); int len=strlen(zimu); for(int i=0;i
C题不能暴力做，会超时（我最开始头铁T了2发）。找规律，如1，2，3，4，5会发现1出现4次，2出现3次，3出现2次，4出现1次。所以先排个序,每个数出现的次数就固定了。 #include #include #include #include #include #include #include #include int a[2600]; int res[3200000]; int num[2600]; using namespace std; bool cmp(int a1,int a2) {   return a1>a2; } int main() {  int n,k,t;  scanf("%d",&t);  for(int i=0;i
D题我还是找规律，其实规律也很简单，就是sum/n（窝太弱了，规律不会证。。。）
#include #include #include #include #include #include #include #include int a[1010]; using namespace std; int main() { int n,t; scanf("%d",&t); for(int i=0;iE题一道dp题，看了赛后给的思路才会做（窝太弱了。。。）。dp[i][j],i表示以i结尾，j表示模为j。线性复杂度，详见代码。（不要忘了开long long）
#include #include #include using namespace std; int dp[1000010][3]; char s[1000010]; int main() { while(scanf("%s",s)!=EOF) { long long int sum=0; if(s[0]=='0') { dp[0][0]=1; dp[0][1]=0; dp[0][2]=0; } else if(s[0]=='1') { dp[0][0]=0; dp[0][1]=1; dp[0][2]=0; } sum+=dp[0][0]; int len=strlen(s); for(int i=1;iF题思路参考了https://blog.csdn.net/qq_40772738/article/details/80034829，用set维护啊，不知道set自带排序，导致比赛时一直TLE。
#include #include #include #include using namespace std; typedef pair P; int a[50010]; int b[50010]; int ok[50010]; int main() { int n,m,q; set

s; while(scanf("%d%d%d",&n,&m,&q)!=EOF) { int ans=0; memset(b,0,sizeof(b)); memset(ok,0,sizeof(ok)); s.clear(); for(int i=0;i::iterator it; it=s.begin(); int tem=(*it).second; s.erase(it); ok[tem]=0; s.insert(P(b[a[i]],a[i])); ok[a[i]]=1; } } else { s.erase(P(b[a[i]],a[i])); b[a[i]]--; s.insert(P(b[a[i]],a[i])); } } printf("%d ",ans); } return 0; } G题很坑，网络赛题的升级版。当时用搜索做的，这次过不了。标程给的dp，我觉得用素数筛更好一些，再加上找规律。就等于n的所有（素数-1）的和。这道题当时没做出来有些可惜~~
#include #include #include #include using namespace std; const int MAXN = 1000000; int prime[MAXN + 1]; void getPrime() { memset(prime, 0, sizeof(prime)); for (int i = 2; i <= MAXN; i++) { if (!prime[i]) { prime[++prime[0]] = i; } for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++) { prime[prime[j] * i] = 1; if (i % prime[j] == 0) { break; } } } return ; } long long factor[100][2]; int fatCnt; int getFactors(long long x) { fatCnt = 0; long long tmp = x; for (int i = 1; prime[i] <= tmp / prime[i]; i++) { factor[fatCnt][1] = 0; if (tmp % prime[i] == 0) { factor[fatCnt][0] = prime[i]; while (tmp % prime[i] == 0) { factor[fatCnt][1]++; tmp /= prime[i]; } fatCnt++; } } if (tmp != 1) { factor[fatCnt][0] = tmp; factor[fatCnt++][1] = 1; } return fatCnt; } int main() { int t,n; scanf("%d",&t); getPrime(); while(t--) { int sum=0; scanf("%d",&n); int len=getFactors(n); for(int i=0;iH，I，J就不写了，本身过的人也不多（比较难）~总结一下就是不会的东西还很多，思路受阻。明年再努力吧~

热门文章