F - K-hour Clock
看完题解就无语了；
x+y-z=dk;
求k；
x+y=z直接最大2e9；
如果说dk比x，z中任意一个小的话，肯定无解；
#include<bits/stdc++.h> #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i++) #define pb push_back using namespace std; typedef long long ll; const int N=1e3+20; int main(){ int t; scanf("%d",&t); while(t--){ ll x,y,z; scanf("%lld %lld %lld",&x,&y,&z); ll ans=x+y-z; if(x+y==z)ans=2e9; else if(ans<=x||ans<=z)ans=-1; printf("%lld ",ans); } return 0; }
B - Grid with Arrows
蛋疼的题，调的我想打人，非要卡内存，动态开了也不过，哈希了之后也不过，dfs也不过，
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; char mp[N]; bool vis[N]; #define ok(x,y) (x>=1&&x<=n&&y>=1&&y<=m) int in[N],out[N],w[N]; int fa[N]; int n,m,dfn; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void build(int x,int y){int dx=find(x),dy=find(y);if(dx!=dy)fa[dx]=dy;} int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); for(int i=1;i<=n*m;i++)fa[i]=i,in[i]=0,out[i]=0; for(int i=1;i<=n;i++){ getchar(); for(int j=1;j<=m;j++){ scanf("%c",&mp[(i-1)*m+j]); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int tmp; scanf("%d",&tmp); int ti=i,tj=j; int ch = mp[(i-1)*m+j]; if(ch=='u') ti = i - tmp; else if(ch=='d') ti = i + tmp; else if(ch=='r') tj = j + tmp; else if(ch=='l') tj = j - tmp; if(ti<1||tj<1||ti>n||tj>m) continue; //越界 build((i-1)*m+j,(ti-1)*m+tj); out[(i-1)*m+j]++;in[(ti-1)*m+tj]++; } bool flag=1; // for(int i=1;i<=n*m;i++)find(i); for(int i=2;i<=n*m;i++){if(find(i)!=find(1))flag=0;} int cnt=0; for(int i=1;i<=n*m;i++)if(in[i]!=out[i])cnt++; if(cnt!=2&&cnt!=0)flag=0; if(flag)puts("Yes"); else puts("No"); } // system("pause"); return 0; }
0689
组合数学，
考虑子串都不重复的情况为 (len+1)*len/2+1；
那么0开头0结尾的去掉，8开头8结尾的去掉，6开头9结尾去掉，9开头6结尾去掉，
有如下式子：
ans-=(n0+1ll)*n0/2;
ans-=(n8+1ll)*n8/2;
ans-=n6*n9;
若全为9或者6任意翻转子串都变不回自己，即ans--;
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; int main(){ int t; scanf("%d",&t); while(t--){ string s; cin>>s; ll len=s.size(); ll ans=(len+1)*len/2+1; ll n0=0,n8=0,n6=0,n9=0; for(int i=0;i<len;i++){ if(s[i]=='0')n0++; else if(s[i]=='6')n6++; else if(s[i]=='8')n8++; else if(s[i]=='9')n9++; } ans-=(n0+1ll)*n0/2; ans-=(n8+1ll)*n8/2; ans-=n6*n9; if(len==n6||len==n9)ans--; printf("%lld ",ans); } // system("pause"); return 0; }
E - Turn It Off
水；注意二分区间；
#include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=1e5+15; typedef long long ll; int n,k; string s; bool check(int L){ int cnt=0; for(int i=0;i<n;i++){ if(s[i]=='1'){cnt++;i+=L-1;} } if(cnt>k)return 0; return 1; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&k); cin>>s; int l=1,r=n; while(l<=r){ int mid=(l+r)/2; if(check(mid))r=mid-1; else l=mid+1; } printf("%d ",l); } // system("pause"); return 0; }
L - Digit Product
水，纯暴力；
#include<bits/stdc++.h> #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i++) #define pb push_back using namespace std; typedef long long ll; const int N=1e3+20; const ll MOD=1e9+7; ll f(ll x){ ll res=1; while(x){ res*=x%10; x/=10; } return res; } int main(){ int t; scanf("%d",&t); while(t--){ ll l,r; scanf("%lld %lld",&l,&r); ll ans=1; if(r-l>=10)ans=0; else { for(ll i=l;i<=r;i++)ans=((ans%MOD)*(f(i)%MOD))%MOD; } printf("%lld ",ans); } // system("pause"); return 0; }
E - Turn It Off
物理题：
最短路径必然在垂直和水平连线上，那么找出他的一个路径重合点d，
纯物理求解最短时间
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; const int N=1e6+5; int main(){ int t; scanf("%d",&t); while(t--){ int va,vb,xa,ya,xb,yb,xc,yc,xd,yd; scanf("%d %d",&va,&vb); scanf("%d %d %d %d %d %d",&xa,&ya,&xb,&yb,&xc,&yc); if(xc>=min(xa,xb)&&xc<=max(xa,xb))xd=xc; else if(fabs(xc-xb)>fabs(xc-xa))xd=xa; else xd=xb; if(yc>=min(ya,yb)&&yc<=max(ya,yb))yd=yc; else if(fabs(yc-yb)>fabs(yc-ya))yd=ya; else yd=yb; db Sad=(fabs(xa-xd)+fabs(ya-yd))*1.0; db Sbd=(fabs(xb-xd)+fabs(yb-yd))*1.0; db Scd=(fabs(xd-xc)+fabs(yd-yc))*1.0; db Sac=(fabs(xa-xc)+fabs(ya-yc))*1.0; db Sbc=(fabs(xb-xc)+fabs(yb-yc))*1.0; double t1=Sac/va; // if(xc>=min(xa,xb)&&xc<=max(xa,xb))xd=xc; // else if(fabs(xc-xb)>fabs(xc-xa))xd=xa; // else xd=xb; // if(yc>=min(ya,yb)&&yc<=max(ya,yb))yd=yc; // else if(fabs(yc-yb)>fabs(yc-ya))yd=ya; // else yd=yb; double t2=0; db td1=Sad/va; db td2=Sbd/vb; if(td1<td2)t2=Sbc/vb; else t2=Sbc/vb+(Sad-Sbd*va/vb)*2/(va+vb); db ans=min(t1,t2); printf("%.7lf ",ans); } // system("pause"); return 0; }
J - Coolbits
题意：挺好的题，给你n各个区间，从每个区间里选取一些数，使得他们&的值最大；
按位与的值最大，那么一定是高位优先，从高位开始枚举，如果所有区间都有一个当前位的1，那么把所有区间的数都变成当前位为1的，
这样就保证了以后枚举较小位的时候满足当前位，神奇的一直缩小区间，
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+5; ll R[N],L[N]; int n; ll c; bool check(ll x){ c+=x; for(int i=1;i<=n;i++){ ll a=L[i],b=R[i]; if((b|x)!=b)b-=x,b|=(x-1); if((a|x)!=a)a+=x,a&=c; if(a>b)return 0; } return 1; } void work(ll x){ for(int i=1;i<=n;i++){ ll a=L[i],b=R[i]; if((b|x)!=b)b-=x,b|=(x-1); if((a|x)!=a)a+=x,a&=c; L[i]=a,R[i]=b; } } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); c=0; for(int i=1;i<=n;i++)scanf("%lld %lld",&L[i],&R[i]); ll ans=0; for(int i=36;i>=0;i--){ if(check(1ll<<i)){ ans+=(1ll<<i); work(1ll<<i); } } printf("%lld ",ans); } // system("pause"); return 0; }