写在前面

我的第六篇博客，记录我在cf第七场比赛。
一共AC了两题：B和C。
被hack了两次，而A是在锁了之后被hack成功的。
排名1351，分数 1530->1505，很难受。

844A. Diversity （模拟）

给定字符串s ( |s|<=1000 ) 和k(1<=k<=26),输出最少将s中的字符更改几个可以使s中有k个以上的不同字符,不可能则输出impossible.

若|s|<k,显然不可能.
统计s中不同的字符个数t,输出min(k-t,0)即可.
写程序时,统计s中重复的字符个数z比较简便,输出min(k-(s-z),0)

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[200]; char s[1010]; int main(void) { int k,z=0; scanf("%s",s); scanf("%d",&k); if(strlen(s)<k) printf("impossible\n"); else { for(int i=0;i<strlen(s);i++) { if(a[s[i]]==0) a[s[i]]++; else z++; } printf("%d\n",max(0,k-(int)(strlen(s)-z)) ); } return 0; }

844B. Rectangles (模拟)

依次组合发现,结果为每行每列2^(1的个数)-1+2^(0的个数)-1,最后减去n*m(单元素集合计算了两次),上限为100*2^50,在int以上ll以下.

讯享网#include <cstdio> #include <iostream> using namespace std; int a[51],b[51]; int main(void) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int tmp; scanf("%d",&tmp); if(tmp) { a[i]++; b[j]++; } } long long ans=0,ll1=1; for(int i=0;i<n;i++) { ans+=(ll1<<a[i])+(ll1<<(m-a[i]))-2; } for(int i=0;i<m;i++) { ans+=(ll1<<b[i])+(ll1<<(n-b[i]))-2; } ans-=m*n; cout << ans <<endl; return 0; }

讯享网

844C. Sorting by Subsequences (离散化,序列环)

#include <bits/stdc++.h> using namespace std; const int M=; int a[M],b[M]; //离散化,传入原数组,存放数组,长度. template <class Typename> void discre(Typename *src, Typename *des, int n) { map<int, int> mp_discre; memcpy(des, src, n * sizeof(stc[0])); sort(des, des + n); for(int i = 0; i < n; i++) mp_discre[des[i]] = i + 1; for(int i = 0; i < n; i++) des[i] = mp_discre[src[i]]; } //需要按照原顺序,可以改用vector set <int> saveloop[M]; //传入需要找环的数组和长度,会被改变.结果储存在saveloop里,返回环数 template <class Typename> int findloop(Typename *a,int n) { int ans=0; for(int i=0;i<n;i++) { int p=i; while(a[p]) { //do something saveloop[ans].insert(a[p]); int last = p; p=a[p]-1; a[last] = 0; } if(!saveloop[ans].empty()) ans++; } return ans; } //传入环数,自动从saveloop调用 void printloop(int ans) { printf("%d\n",ans ); for(int i=0;i<ans;i++) { int len=saveloop[i].size(); printf("%d",len ); for(auto j:saveloop[i]) cout <<' ' << j; printf("\n"); } } int main(void) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); discre(a,b,n); int ans=findloop(b,n); printloop(ans); return 0; }

844D. Interactive LowerBound (交互题,随机)

给定一个长为n(50000)的单链表,以及他的开头的位置start,需要查找的数x,通过最多2000次交互求x的lower_bound.
单链表:若干个存放两个数的位置:值vi,下个数的位置nexi,保证v(nexi)>vi,(1<=n<=n).
交互两种操作:
输出 ? i 会给出vi和 nexi,当vi是最大时nex=-1.(最多1999次)
输出 ! ans ,表示给出结果.
每次输出后需要调用fflush(stdout).

首先明确要求,lower_bound需要找到大于等于x的第一个值,即如果vi<x且v(nexi)>=x,答案就是v(nexi).
进行一次(? start),特判一次.然后随机999个i输出(? i),选择返回的结果里最大的小于等于x的值.从该值开始求最多999个nex,找到lower_bound(x)或者-1停止.
概率分析:随机时只要随机到[x的排序-999,x的排序]之内的任意一个数即可,一共有n个数,找不到的概率为(1-999/n)^999,代入n=50000计算,约为1e-9(0.00000000175)

讯享网#include <bits/stdc++.h> using namespace std; int sec(int a, int b, int x) { if(a > b && a <= x) return 1; return 0; } pair<int, int> get(int index) { printf("? %d\n", index ); fflush(stdout); int tv, tn; scanf("%d %d", &tv, &tn); if(tv == -1 && tn == -1) exit(0); return {tv, tn}; } int main(void) { srand(time(0)); int n, start, x, time = 999; scanf("%d%d%d", &n, &start, &x); pair<int, int> now = get(start), tmp; if(now.first >= x) { printf("! %d\n", now.first ); return 0; } for(int i = 1; i < 1000; i++) { tmp = get((rand() + rand()) % n + 1); if(sec(tmp.first, now.first, x)) now = tmp; } tmp = now; while(time--) { if(tmp.first <= x && now.first >= x) { printf("! %d\n", now.first); return 0; } if(now.second == -1) break; tmp = now; now = get(tmp.second); } printf("! -1\n"); return 0; }

下午写的代码,但是陷入了一个比较难察觉的逻辑bug中,晚上才找到.
写题之前还通过群里讨论避免了一个bug:cf的rand()似乎只能到32767.
考虑一下以后把逻辑图先画好?
代码用时(如果没有逻辑bug):40分钟
debug时间:2小时.

总结

常数移位也会溢出,程序的需求与逻辑结构一定要理清楚.
关于cf:锁题也在一定程度上意味着失去了被hack帮忙找bug的机会.
rand()最大值32767.,可以通过乘或加来实现大数的随机.