6月19日 cf总结
昨天打了两场cf，一场vp和一场半夜的contest。
每次vp都打的不错，一到contest就不行了，唉。。昨天vp差点就三题rank前50了，c题交慢了13秒，而且做c题的时候是在干扰下做的，而且是靠别人翻译题意翻译错被坑了很多时间的情况下，虽然c题没交上去，但是两题手速也不算慢了，也rank327，当然自己对A题题意看半天11分钟才过以及B题一开始没看到c样例稍理解错题意浪费了点时间，以及测试数据的时候动作太慢有浪费了很多时间拉低了手速也是不太满意，要是测试的时候快点，说不定AB两题从看题到写代码到提交加起来不到20分钟就搞定了。c题一开始被坑了题意，理解正确后建图又手写了拓排(模版有点问题。。)，最后没注意重边，到发现重边的时候交上去就过了，不过已经比赛结束了，提交无效，略可惜。这场当时没打真是可惜，要是放到现在打的话说不定就一场紫了，还有前面打的几场vp也是，每次打vp都比较顺，手速也比较快，一到半夜打contest就不行了，各种看不懂题意，各种没思路，各种不想写想睡觉。。。而且运气也不是特别好，碰到的都是不熟悉的题。
再说昨天晚上的contest，本来打完vp应该是很有信心的，然而昨天晚上的contest真是太惨了。。。
A题看了半天没懂题意，看懂了题意又以一种手速最慢的方法过，题意看了10分钟代码写了3分钟第13分钟才过A，要是白天的话不超过5分钟吧。。。再看B，题意倒是不难，但是关灯了，没计算纸怎么写。。。于是在头脑中意淫半天终于在1个小时左右过了B。。。运气太差了。。。如果不再过一题肯定掉rating了，，于是开了d，很可惜，思路对了，没计算纸加上时间浪费在e题上最后没时间了，本来d也要是白天做的话是可以过的，关键是半夜关灯没法在纸上计算啊。。。过了d即时手速慢rating也能涨到蓝啊。。。。最后只过两题，而且手速还很慢，好惨。。。
以下是题解，代补充。。。
下面是#308
A题：
水题，本来计算一个矩阵的(x1,y1)到(x2,y2)的格子数(左上角到右下角)直接（x2-x1+1)*(y2-y1+1)就行了，比赛的时候脑子进水，直接两层循环。。。简直无语。。。。
B题：
将数字按位来数，写出顺位。比如9->9 10->11 11->13 ,因为10和11是两位数，所以比前面增加了2。
思路：对一个数比如235426，这是一个六位数，先计算它前面的五位数数了多少，即1-9(9*1)，10->99(90*2)，100->999(900*3)，1000->9999(9000*4)，10000->99999(90000*5)，可以直接计算或者预处理，再计算六位数的情况即 100000 -> 235426 ((235426-100000)*6) ，所有结果加起来即可。
比赛的时候由于没有计算纸，过程全在脑子里意淫，代码写得实在是惨不忍睹。。。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",s) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (v).size() using namespace std; const int maxn=1000100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); ll n; ll cnt[maxn]; int digit(ll n) { if(n==0) return 1; int res=0; while(n){ n/=10; res++; } return res; } ll mp(ll n,ll k) { ll res=1; while(k--) res*=n; return res; } ll f(ll n) { int d=digit(n); if(d==1) return n; ll res=0; res+=cnt[d-2]; ll nt=mp(10,d-1); res+=(n-nt+1)*d; return res; } void Init() { MS0(cnt); cnt[0]=9; REP(i,1,10){ cnt[i]=cnt[i-1]+(mp(10,i+1)-mp(10,i))*(i+1); } } int main() { Init(); while(cin>>n){ cout<<f(n)<<endl; } return 0; }
C题：
给一个天平和一个重量为m的重物，以及一些重量为w^0，w^1，w^2,....,w^100的砝码，每种砝码只有一个，求将重物放在一端，将一些砝码放在天平两端是否能使天平平衡。
思路：比赛的时候想用背包，但是又爆了longlong，就直接放弃了。。。正解是进制的，m能用w^i表示且最多每个只出现一次即系数为0,1或-1，将m表示成w进制的数，每一位上只能有0,1,w-1，按十进制类比，比如但如果出现19，19=10+9=2*(10^1)-10^0，显然不符合，所以只要出现w-1时加上1即可知道后面的系数。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",s) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (v).size() using namespace std; const int maxn=1000100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); ll w,m; int main() { while(cin>>w>>m){ bool flag=1; while(m){ ll t=m%w; if(t!=0&&t!=1&&t!=w-1){ flag=0;break; } if(t==w-1&&t!=1) m++; m/=w; } puts(flag?"YES":"NO"); } return 0; }
比赛的时候真不应该放弃这题，直接01背包+java高精度应该也是可以过的。
D题：
这题比赛的时候应该是略超出我的水平了，要超常发挥的话才做的出来，超出自己水平的部分是如何把三点共线用hash优化，方法是用PII存斜率并约分而不是用double，再用map，现在学了这个这道题应该是在自己的水平之内了，注意下longlong就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",s) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (v).size() using namespace std; const int maxn=1000100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); int n; struct Point { int x,y; friend Point operator+(Point A,Point B) { return {A.x+B.x,A.y+B.y}; } friend int operator*(Point A,Point B) { return A.x*B.y-A.y*B.x; } friend Point operator-(Point A,Point B) { return {A.x-B.x,A.y-B.y}; } }; Point p[maxn]; map<PII,ll> m; int main() { while(cin>>n){ REP(i,1,n) RII(p[i].x,p[i].y); ll ans=(ll)n*(n-1)*(n-2)/6; REP(i,1,n-1){ m.clear(); REP(j,i+1,n){ Point t=p[i]-p[j]; ll g=__gcd(abs(t.x),abs(t.y)); t.x/=g;t.y/=g; if(t.x<0){ t.x=-t.x; t.y=-t.y; } else if(t.x==0){ if(t.y<0) t.y=-t.y; } ans-=m[{t.x,t.y}]; m[{t.x,t.y}]++; } } cout<<ans<<endl; } return 0; }
下面是#290的vp
A题，水题
B题，dfs水题，判断是否存在环
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",s) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (v).size() using namespace std; const int maxn=100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); int n,m; const int R=0,D=1,L=2,U=3; char ch[maxn][maxn]; bool vis[maxn][maxn]; bool tag; bool dfs(int x,int y,char c,int dir) { if(ch[x][y]=='#'||ch[x][y]!=c) return 0; if(vis[x][y]&&ch[x][y]==c) return tag=1; //cout<<"x="<<x<<" y="<<y<<endl; vis[x][y]=1; if(dir==R) return dfs(x,y+1,c,R)||dfs(x+1,y,c,D)||dfs(x-1,y,c,U); if(dir==D) return dfs(x+1,y,c,D)||dfs(x,y-1,c,L)||dfs(x,y+1,c,R); if(dir==L) return dfs(x,y-1,c,L)||dfs(x-1,y,c,U)||dfs(x+1,y,c,D); if(dir==U) return dfs(x-1,y,c,U)||dfs(x,y+1,c,R)||dfs(x,y-1,c,L); vis[x][y]=0; } int main() { while(cin>>n>>m){ MS(ch,'#'); MS0(vis); tag=0; bool flag=0; REP(i,1,n) REP(j,1,m) cin>>ch[i][j]; REP(i,1,n){ REP(j,1,m){ MS0(vis); if(dfs(i,j,ch[i][j],R)) flag=1; if(flag) break; } if(flag) break; } puts(flag?"Yes":"No"); } return 0; }
C题，求构造新字典序使给定的一些字符串的顺序能符合新的字典序的顺序。
思路：建图，然后拓扑排序，输出拓扑序列，注意下建图时的判断就可以了，注意去掉重边的入度。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",s) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (v).size() using namespace std; const int maxn=120; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); bool G[maxn][maxn]; int n; string s[maxn]; bool vis[maxn]; int deg[maxn]; vector<int> ans; bool toposort() { queue<int> q; MS0(vis); REP(i,0,25){ if(deg[i]==0){ q.push(i); ans.PB(i); vis[i]=1; deg[i]--; } } while(!q.empty()){ int u=q.front();q.pop(); REP(v,0,25)if(G[u][v]){ if(--deg[v]==0){ ans.PB(v); q.push(v); vis[v]=1; } } } REP(i,0,25) if(!vis[i]) return 0; return 1; } int main() { while(cin>>n){ ans.clear(); REP(i,1,n){ cin>>s[i]; } MS0(deg); bool flag=1; REP(i,2,n){ if(s[i]==s[i-1]) continue; int len=min(SZ(s[i]),SZ(s[i-1])); bool tag=0; REP(j,0,len-1){ if(s[i-1][j]!=s[i][j]){ tag=1; if(!G[s[i-1][j]-'a'][s[i][j]-'a']){ G[s[i-1][j]-'a'][s[i][j]-'a']=1; deg[s[i][j]-'a']++; } break; } } if(!tag&&SZ(s[i-1])>SZ(s[i])){ flag=0;break; } } if(flag&&toposort()){ REP(i,0,SZ(ans)-1) cout<<(char)(ans[i]+'a'); puts(""); } else puts("Impossible"); } return 0; }