A - ArcSoft's Office Rearrangement
均分石子。
好像怎么分答案都一样，于是模拟一遍。#includeusing namespace std;typedef long long ll;template inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template inline void read(A&x,B&y){read(x);read(y);}template inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}ll a[100005],n,k,x;ll s;int main(){ //freopen("in.txt","r",stdin); int T,cas=1; cin>>T; while(T--){ read(n,k); s=0; for(int i=1;i<=n;i++) read(a[i]),s+=a[i]; if(s%k!=0){ printf("Case #%d: -1\n",cas++); continue; } ll cmp = s / k; ll ans = 0; for(int i=1;i<=n;i++){ if(a[i]==cmp) continue; if(a[i]
B - Bomb
Tarjan之后算一下不同scc里面的cost。
#includeusing namespace std;typedef long long ll;struct infonode { ll x,y,r,d;}info[2005];struct tarjan { const static int maxn = 2e4+7; const static int maxm = 2e6+7; struct Edge { int to,nxt; Edge(){} Edge(int _to,int _nxt):to(_to),nxt(_nxt){} }edge[maxm]; int head[maxn],tot,n; int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn]; int Index,top; int scc; int num[maxn]; bool Instack[maxn]; int Min[maxn]; inline void init(int n) { tot = 0;this->n=n; memset(head,-1,sizeof head); } inline void addedge(int u,int v) { edge[tot]=Edge(v,head[u]); head[u]=tot++; } void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i=head[u];i!=-1;i=edge[i].nxt){ v = edge[i].to; if(!DFN[v]){ Tarjan(v); Low[u]=min(Low[u],Low[v]); } else if(Instack[v] && Low[u]>DFN[v]){ Low[u]=DFN[v]; } } if(Low[u]==DFN[u]){ scc++; do{ v=Stack[--top]; Instack[v]=false; Belong[v]=scc; num[scc]++; }while(v!=u); } } int indeg[maxn]; inline ll solve(int n){ memset(DFN,0,sizeof DFN); memset(num,0,sizeof num); memset(Instack,0,sizeof Instack); Index = scc = top = 0; for(int i=1;i<=n;i++) if(!DFN[i]) Tarjan(i); memset(indeg,0,sizeof indeg); //if(scc==1) return 0; for(int u=1;u<=n;u++) for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(Belong[u]!=Belong[v]){ indeg[Belong[v]]++; } } memset(Min,63,sizeof Min); for(int i=1;i<=n;i++) Min[Belong[i]]=min((ll)Min[Belong[i]],info[i].d); ll ret = 0; for(int i=1;i<=scc;i++) if(indeg[i]==0) ret += (ll)Min[i]; return ret; }} g;int n,cas=1;template inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template inline void read(A&x,B&y){read(x);read(y);}template inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}int main(){ //freopen("in.txt","r",stdin); int T; read(T); while(T--){ read(n); g.init(n); for(int i=1;i<=n;i++) read(info[i].x,info[i].y,info[i].r,info[i].d); for(int i=1;i
C - Car
模拟分数，否则卡精度，因为涉及多次除被除除。。。
#include#define maxn 100050using namespace std;typedef long long LL;int t,n;int a[maxn];int Case=1;int main(){ //freopen("in.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); LL fenzi=a[n]-a[n-1],fenmu=1; LL time=1; for(int i=n-1;i>=1;i--){ LL d=a[i]-a[i-1]; fenmu*=d; LL tmp=fenmu/fenzi; if(fenmu%fenzi!=0) tmp++; time+=tmp; fenzi=d; fenmu=tmp; } printf("Case #%d: %lld\n",Case++,time); } return 0;}
D - Difference
每个k预处理一半，然后用中途相遇法，就是类似尺取。
#includeusing namespace std;typedef long long ll;ll a[10][100005],b[10][100005];ll base[11];ll P[11][11];template inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template inline void read(A&x,B&y){read(x);read(y);}template inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}void init(){ base[0]=1; for(int i=1;i<=10;i++) base[i]=base[i-1]*10ll; for(int i=0;i<=9;i++){ P[i][1]=i; for(int j=2;j<=9;j++) P[i][j]=P[i][j-1]*i; } for(int kk=1;kk<=9;kk++){ for(int i=0;i<=99999;i++){ a[kk][i]=P[i%10][kk]+P[i%100/10][kk]+P[i%1000/100][kk]+P[i%10000/1000][kk] +P[i%100000/10000][kk]-(ll)i*100000ll; b[kk][i]=P[i%10][kk]+P[i%100/10][kk]+P[i%1000/100][kk]+P[i%10000/1000][kk] +P[i%100000/10000][kk]-i; } } for(int i=1;i<=9;i++){ sort(a[i],a[i]+100000); sort(b[i],b[i]+100000); }}int main(){ //freopen("in.txt","r",stdin); init(); int T,k,cas=1; ll x; cin>>T; while(T--){ read(x,k); ll res = 0; for(int l=0,r=99999;l<=99999 && r;){ if(a[k][l]+b[k][r]>x) r--; else if(a[k][l]+b[k][r]
F - Four Operations
贪心+枚举。
#includeusing namespace std;typedef long long ll;int cas=1;char s[55];int main(){ //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%s",s+1); int len=strlen(s+1); ll ans = -INT_MAX; for(int i=1;i<=len-4;i++){ for(int j=i+1;j<=len-3;j++){ ll A=0,B=0,C=0,D=0,E=0; for(int c=1;c<=i;c++) A=A*10ll+s[c]-'0'; for(int c=i+1;c<=j;c++) B=B*10ll+s[c]-'0'; C=s[j+1]-'0'; D=s[j+2]-'0'; for(int c=j+3;c<=len;c++) E=E*10ll+s[c]-'0'; ll tmp = A + B - C * D / E; ans = max(ans,tmp); } } printf("Case #%d: ",cas++); cout< <
K - Kingdom of Obsession
二分图匹配，建立匹配边就行。
若有交合部分，s<n 实际上可以由(1...n)-(s+1...s+n)变成(1...s)-(n+1,...,n+s)，中间部分自己匹配。#includeusing namespace std;typedef long long ll;const int maxn = 1005;int matches[maxn];int link[maxn][maxn];bool used[maxn];int n,s;bool find(int x){ for(int j=1;j<=n;j++){ if(link[x][j] && used[j]==false){ used[j]=1; if(matches[j]==0 || find(matches[j])){ matches[j]=x; return 1; } } } return 0;}int main(){ //freopen("in.txt","r",stdin); int T,cas=1; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&s); if(s==0){ printf("Case #%d: Yes\n",cas++); continue; } if(n>s) swap(n,s); if(n>1000) printf("Case #%d: No\n",cas++); else { memset(link,0,sizeof link); memset(matches,0,sizeof matches); for(int i=s+1;i<=s+n;i++){ for(int j=1;j<=n;j++) if(i%j==0) link[j][i-s]=1; } int res = 0; for(int i=1;i<=n;i++){ memset(used,0,sizeof used); if(find(i)) res++; } if(res==n){ printf("Case #%d: Yes\n",cas++); } else { printf("Case #%d: No\n",cas++); } } } return 0;}