首页 > 代码库 > CSU-ACM暑假集训基础组训练赛(2) 解题报告
CSU-ACM暑假集训基础组训练赛(2) 解题报告
Problem A Codeforces 451A
•题意：给你n+m根筷子，将他们分别水平、垂直放置，形成n*m个节点。两个人轮流选择一个点，将穿过这个点的两根筷子拿走，谁可以逼迫对方率先无法继续操作，谁就获胜，问获胜的是先手还是后手。
•找规律即可。n,m中较小的那个数是奇数，先手胜，否则后手胜。
1 #include <cstdio>2 int main(){3 int a,b;4 scanf("%d%d",&a,&b);5 a = a < b ? a : b;6 printf(a&1 ? "Akshat" : "Malvika");7 return 0;8 }
Problem B Codeforces 451B
•题意：给你一个长度不超过10^5的数组，数组中的每个元素互不相同。
•问是否能翻转数组的某个区间，使得数组形成一个有序的升序序列。
•先按数组元素值的大小排序
•排完序之后，就能形成一个序列id[i]
•id[i]表示第i个数字在数组中的大小排名第几
•比如说:
•a[1]=1,a[2]=10,a[3]=6,a[4]=2,a[5]=11
•id[1]=1,id[2]=4,id[3]=3,id[4]=2,id[5]=5
•a[1]=1,a[2]=10,a[3]=6,a[4]=2,a[5]=11
•id[1]=1,id[2]=4,id[3]=3,id[4]=2,id[5]=5
•于是我们发现，如果我们能将id区间的某一段翻转过后，使得id[i]=i，那么就可以找到满足题意的区间
•找左端点L：第一个id[i]不等于i的端点
•找右端点R：第一个id[i]-id[i+1]不等于1的端点
•接下来我们需要验证剩余的i>R,id[i]是否等于i
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 100010; 5 struct Node{ 6 int val,id; 7 bool operator < (const Node& rhs) const{ 8 return val < rhs.val; 9 }10 }node[maxn];11 12 int main(){13 int n,l = -1,r;14 bool flag = 1;15 scanf("%d",&n);16 for(int i = 1;i <= n;i++){17 scanf("%d",&node[i].val);18 node[i].id = i;19 }20 sort(node+1,node+n+1);21 node[n+1].id = -1;22 for(int i = 1;i <= n;i++){23 if(node[i].id != i){24 l = i;25 break;26 }27 }28 if(l == -1){29 printf("yes\n1 1\n");30 return 0;31 }32 for(int i = l;i <= n;i++){33 if(node[i].id - node[i+1].id != 1){34 r = i;35 break;36 }37 }38 for(int i = r+1;i <= n;i++){39 if(node[i].id != i){40 flag = false;41 break;42 }43 }44 if(flag) printf("yes\n%d %d\n",l,r);45 else printf("no\n");46 return 0;47 }
Problem C FZU 1907
•题意：给你一个字符串str，对于每个str长度为p的前缀，如果str[i]==str[p+i](p+i<len)，那么我们认为它是一个periodic prefixs.求所有满足题意的前缀的长度p。
•知识点：KMP算法、对next数组的理解
•KMP算法中next数组的含义是什么？
•next数组：失配指针
•如果目标串的当前字符i在匹配到模式串的第j个字符时失配，那么我们可以让i试着去匹配next(j)
•对于模式串str，next数组的意义就是：
•如果next(j)=t,那么str[1…t]=str[len-t+1…len]
•我们考虑next(len)，令t=next(len);
•next(len)有什么含义？
•str[1…t]=str[len-t+1…len]
•那么，长度为len-next(len)的前缀显然是符合题意的。
•接下来我们应该去考虑谁？
•t=next( next(len) );
•t=next( next (next(len) ) );
• 一直下去直到t=0,每个符合题意的前缀长是len-t
1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 1000010; 4 int p[maxn],ans[maxn]; 5 char str[maxn]; 6 7 void get_p(int len){ 8 p[1] = 0; 9 int j = 0;10 for(int i = 2;i <= len;i++){11 while(j > 0 && str[j+1] != str[i]) j = p[j];12 if(str[j+1] == str[i]) j++;13 p[i] = j;14 }15 }16 17 int main(){18 int nkase;19 scanf("%d",&nkase);20 for(int kase = 1;kase <= nkase;kase++){21 scanf("%s",str+1);22 int len = strlen(str+1);23 get_p(len);24 int t = p[len],cnt = 0;25 while(t){26 ans[cnt++] = len-t;27 t = p[t];28 }29 ans[cnt++] = len;30 printf("Case #%d: %d\n",kase,cnt);31 for(int i = 0;i < cnt-1;i++) printf("%d ",ans[i]);32 printf("%d\n",ans[cnt-1]);33 }34 return 0;35 }
Problem D UVA 10608
•题意：一个镇上有N个人，他们之间有M组朋友关系。有一句名言说：“我朋友的朋友也是我的朋友”。问朋友最多的那个人能有多少朋友。
•考察内容：并查集的基本操作
•并操作
•查操作
•维护一个集合内元素的数量
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 30010; 5 int fa[maxn],num[maxn],ans; 6 7 int find(int u){ 8 return fa[u] == u ? u : fa[u] = find(fa[u]); 9 }10 11 void Union(int u,int v){12 int a = find(u);13 int b = find(v);14 if(a != b){15 fa[a] = b;16 num[a] += num[b];17 num[b] = num[a];18 ans = max(ans,num[b]);19 }20 }21 22 int main(){23 int kase,n,m,a,b;24 scanf("%d",&kase);25 while(kase--){26 scanf("%d%d",&n,&m);27 for(int i = 1;i <= n;i++){28 fa[i] = i;29 num[i] = 1;30 }31 ans = 0;32 for(int i = 0;i < m;i++){33 scanf("%d%d",&a,&b);34 Union(a,b);35 }36 printf("%d\n",ans);37 }38 return 0;39 }
Problem E Codeforces 237C
•题意：给你一个闭区间[a,b]，求一个最小的L，使得在区间[a,b-L+1]内任取一个数x，可以满足在x,x+1,x+2,……,x+L-2,x+L-1内至少包含k个素数。(1<=a,b,k<=10^6)
•
•考察内容：筛素数、二分
•View Code
•一边筛素数，一边处理出一个前缀和sum
•sum(i)表示[1,i]中有多少素数
•那么我们每次查询区间[l,r]中有多少素数，直接查sum[r]-sum[l-1]就可以了
•接下去我们按照题意，对答案L进行二分就可以了
1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 1000010; 4 int sum[maxn],a,b,k; 5 bool pri[maxn]; 6 void init(){ 7 for(int i = 2;i < maxn;i++){ 8 sum[i] = sum[i-1]; 9 if(pri[i]) continue;10 sum[i]++;11 for(int j = i+i;j < maxn;j += i)12 pri[j] = 1;13 }14 }15 16 bool check(int mid){17 for(int i = a;i <= b-mid+1;i++){18 if(sum[i+mid-1]-sum[i-1] < k) return 0;19 }20 return 1;21 }22 23 int main(){24 init();25 scanf("%d%d%d",&a,&b,&k);26 if(sum[b]-sum[a-1] < k){27 printf("-1\n");28 return 0;29 }30 int l = 1,r = b-a+1,ans;31 while(l <= r){32 int mid = (l+r)>>1;33 if(check(mid)) ans = mid,r = mid-1;34 else l = mid+1;35 }36 printf("%d\n",ans);37 }
Problem F Codeforces 16E
•题意：有n(n<=18)条鱼，接下来的n-1天，每天会有一对鱼(a,b)相遇，每天任意一对鱼相遇的概率是相等的，相遇之后，他们其中的一条会吃掉另外一条。
•鱼a吃掉鱼b的概率是p，那么鱼b吃掉鱼a的概率就是1-p;
•给你一个n*n的矩阵，表示n条鱼中的某对相遇时，互相吃掉对方的概率。
•数据保证pij+pji=1;
•计算每只鱼最后存活下来的概率。
•status{x1,x2,x3,x4,………xn-1,xn}表示每只鱼是否还活着的状态
•xi=1表示第i条鱼还活着
•xi=0表示第i条鱼已经被吃掉了
•dp(status)表示形成status这种状态的概率
•那么刚开始的时候（第一天），所有的鱼都活着。
•那么dp({1,1,1,1….,1,1,1})=1。
•View Code
•假设当前状态status活着的鱼有t条
•此时，如果鱼j活着，鱼k也活着，那么j把k吃掉的概率是多少呢？
•P(j吃掉k)=P(j,k相遇)*P(相遇时j可以吃掉k)=1/C(t,2)*P(相遇时j可以吃掉k)
•dp(newstatus) += P(j吃掉k)*dp(status)
•newstatus:j吃掉k之后的新状态
1 #include <cstdio> 2 #include <cstring> 3 double dp[1<<18]; 4 double mat[18][18]; 5 6 int bitcount(int t){ 7 int ret = 0; 8 while(t){ 9 ret += t&1;10 t >>= 1;11 }12 return ret;13 }14 15 int main(){16 int n;17 scanf("%d",&n);18 for(int i = 0;i < n;i++){19 for(int j = 0;j < n;j++){20 scanf("%lf",&mat[i][j]);21 }22 }23 dp[(1<<n)-1] = 1;24 for(int i = (1<<n)-1;i >= 1;i--){25 int bit = bitcount(i);26 if(bit == 1) continue;27 double p = 2*dp[i]/bit/(bit-1);28 for(int j = 0;j < n;j++)if(i&(1<<j)){29 for(int k = 0;k < n;k++)if(i&(1<<k)){30 dp[i^(1<<k)] += p*mat[j][k];31 }32 }33 }34 for(int i = 0;i < n;i++){35 printf("%.6f ",dp[1<<i]);36 }37 return 0;38 }
CSU-ACM暑假集训基础组训练赛(2) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。