A 签到，注意%k
1 #include <bits/stdc++.h> 2 const long long mod = 1e9+7; 3 const double ex = 1e-10; 4 #define inf 0x3f3f3f3f 5 using namespace std; 6 long long a[112345]; 7 int main() 8 { 9 int T; 10 cin >> T; 11 for (int cas = 1; cas<=T; cas++){ 12 int N; 13 long long K; 14 printf("Case #%d: ",cas); 15 long long sum = 0; 16 scanf("%d%I64d",&N,&K); 17 for (int i = 1; i<=N; i++){ 18 scanf("%I64d",&a[i]); 19 sum+=a[i]; 20 } 21 if (sum%K){ 22 printf("%d ",-1); 23 continue; 24 } 25 K = sum/K; 26 sum = 0; 27 long long num = 0; 28 long long ans = 0; 29 for (int i = 1; i<=N;i++){ 30 sum+=a[i]; 31 if (sum%K==0) { 32 ans+=((sum/K)-1); 33 sum=0; 34 } else 35 ++ans; 36 } 37 printf("%I64d ",ans); 38 } 39 return 0; 40 }
B 有向图强连通
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=1005; 4 int T,V,n,c[maxn],cmp[maxn],boom[maxn],deg[maxn]; 5 vector<int> G[maxn],rG[maxn],vs; 6 bool used[maxn]; 7 long long x[maxn],y[maxn],r[maxn]; 8 void addedge(int from,int to) { 9 G[from].push_back(to); 10 rG[to].push_back(from); 11 } 12 void dfs(int v) { 13 used[v]=true; 14 for (int i=0;i<(int)G[v].size();++i) 15 if (!used[G[v][i]]) 16 dfs(G[v][i]); 17 vs.push_back(v); 18 } 19 void rdfs(int v,int k) { 20 used[v]=true; 21 cmp[v]=k; 22 for (int i=0;i<(int)rG[v].size();++i) 23 if (!used[rG[v][i]]) 24 rdfs(rG[v][i],k); 25 } 26 inline int scc() { 27 memset(used,0,sizeof used); 28 vs.clear(); 29 for (int v=0;v<V;++v) 30 if (!used[v]) 31 dfs(v); 32 memset(used,0,sizeof used); 33 int k=0; 34 for (int i=vs.size()-1;i>=0;--i) 35 if (!used[vs[i]]) 36 rdfs(vs[i],k++); 37 return k; 38 } 39 inline bool check(int i,int j) { 40 if ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=r[i]*r[i]) 41 return true; 42 return false; 43 } 44 int main() 45 { 46 scanf("%d",&T); 47 for (int cas=1;cas<=T;++cas) { 48 scanf("%d",&n); 49 V=n; 50 for (int i=0;i<n;++i) { 51 G[i].clear(); 52 rG[i].clear(); 53 } 54 for (int i=0;i<n;++i) 55 scanf("%I64d%I64d%I64d%d",&x[i],&y[i],&r[i],&c[i]); 56 for (int i=0;i<n;++i) 57 for (int j=0;j<n;++j) if (i!=j) 58 if (check(i,j)) 59 addedge(i,j); 60 memset(cmp,-1,sizeof cmp); 61 memset(boom,0x3f,sizeof boom); 62 memset(deg,0,sizeof deg); 63 int sz=scc(); 64 for (int i=0;i<n;++i) 65 boom[cmp[i]]=min(boom[cmp[i]],c[i]); 66 for (int i=0;i<n;++i) 67 for (int j=0;j<(int)G[i].size();++j) { 68 int v=G[i][j]; 69 if (cmp[i]!=cmp[v]) 70 ++deg[cmp[v]]; 71 } 72 int res=0; 73 for (int i=0;i<sz;++i) 74 if (!deg[i]) 75 res+=boom[i]; 76 printf("Case #%d: %d ",cas,res); 77 } 78 return 0; 79 }
C 倒着递推，设最后一次的时间为1
1 #include <bits/stdc++.h> 2 const int inf = 0x3f3f3f3f3f3f3f3f; 3 using namespace std; 4 const double eps=1e-16; 5 const int maxn=100005; 6 int T,n; 7 long long a[maxn]; 8 int main() 9 { 10 scanf("%d",&T); 11 for (int cas=1;cas<=T;++cas) { 12 scanf("%d",&n); 13 for (int i=1;i<=n;++i) 14 scanf("%I64d",&a[i]); 15 long long res=0,time=1;; 16 a[n+1] = inf; 17 for (int i=n;i>=1;--i){ 18 time = (( a[i] - a[i-1] ) * time + a[i+1]-a[i]-1 ) / (a[i+1] - a[i]); 19 res+=time; 20 } 21 printf("Case #%d: %I64d ",cas,res); 22 } 23 return 0; 24 }
D 拆成两部分，前五位 和 后五位，预处理+查找，map竟然超时，垃圾STL
1 #include <bits/stdc++.h> 2 using namespace std; 3 int T,K,x,F[10][100001],fact[10][10]; 4 vector<long long> v; 5 inline int calc(int x,int k) { 6 int ret=0; 7 while (x) { 8 int now=x%10; 9 ret+=fact[now][k]; 10 x/=10LL; 11 } 12 return ret; 13 } 14 int main() 15 { 16 //freopen("in.txt","r",stdin); 17 for (int i=1;i<=9;++i) 18 fact[i][0]=1; 19 for (int i=1;i<=9;++i) 20 for (int j=1;j<=9;++j) 21 fact[i][j]=fact[i][j-1]*i; 22 for (int i=1;i<=9;++i) 23 for (int j=0;j<=100000;++j) 24 F[i][j]=calc(j,i); 25 scanf("%d",&T); 26 for (int cas=1;cas<=T;++cas) { 27 v.clear(); 28 scanf("%d%d",&x,&K); 29 for (int i=0;i<100000;++i) 30 v.push_back(i-F[K][i]); 31 sort(v.begin(),v.end()); 32 int res=0; 33 for (int i=0;i<=100000;++i) { 34 long long ask=F[K][i]-100000LL*i-x; 35 res+=upper_bound(v.begin(),v.end(),ask)-lower_bound(v.begin(),v.end(),ask); 36 } 37 printf("Case #%d: %d ",cas,res-(x==0)); 38 } 39 return 0; 40 }
E 暴力出奇迹
1 #include <bits/stdc++.h> 2 using namespace std; 3 int T,p[36][3],cnt[10],now[10],res; 4 inline void change(int x,int v) { 5 for (int i=0;i<3;++i) 6 now[p[x][i]]+=v; 7 } 8 inline bool check(int x) { 9 bool flag=true; 10 for (int i=0;i<3;++i) { 11 --now[p[x][i]]; 12 if (now[p[x][i]]<0) 13 flag=false; 14 } 15 for (int i=0;i<3;++i) 16 ++now[p[x][i]]; 17 return flag; 18 } 19 inline void init() { 20 int x=0; 21 for (int i=1;i<10;++i) 22 for (int j=1;j+i<10;++j) { 23 p[x][0]=i; 24 p[x][1]=j; 25 p[x++][2]=i+j; 26 ++cnt[i]; 27 ++cnt[j]; 28 ++cnt[i+j]; 29 } 30 } 31 void dfs(int u,int v) { 32 res=max(res,v); 33 if (36-u+v<=res||u>36) 34 return; 35 if (check(u)) { 36 change(u,-1); 37 dfs(u+1,v+1); 38 change(u,1); 39 } 40 dfs(u+1,v); 41 } 42 int main() 43 { 44 init(); 45 scanf("%d",&T); 46 for (int cas=1;cas<=T;++cas) { 47 for (int i=1;i<=9;++i) { 48 scanf("%d",&now[i]); 49 now[i]=min(now[i],cnt[i]); 50 } 51 res=0; 52 dfs(0,0); 53 printf("Case #%d: %d ",cas,res); 54 } 55 return 0; 56 }
F贪心
1 #include <bits/stdc++.h> 2 #define maxn 100010 3 #define inf 0x3f3f3f3f 4 #define REP(i,x,y) for(int i=x;i<(y);i++) 5 #define RREP(i,x,y) for(int i=x;i>(y);i--) 6 using namespace std; 7 typedef long long ll; 8 typedef pair<int,int> pii; 9 char s[50]; 10 int main() 11 { 12 int T,cas=1;scanf("%d",&T); 13 while(T--) { 14 scanf(" %s",s+1);int len=strlen(s+1); 15 ll ans=-inf; 16 for(int pos=2;pos<=len-3;pos++) { 17 ll res1=0; 18 for(int i=2;i<=pos;i++) { 19 res1=res1*10+(s[i]-'0'); 20 } 21 res1+=s[1]-'0'; 22 ll res2=0; 23 for(int i=1;i<=pos-1;i++) { 24 res2=res2*10+(s[i]-'0'); 25 } 26 res2+=s[pos]-'0'; 27 ll maxx=max(res1,res2); 28 // cout<<res1<<" "<<res2<<" "<<maxx<<endl; 29 ll sub=(s[pos+1]-'0')*(s[pos+2]-'0'); 30 ll divide=0; 31 for(int i=pos+3;i<=len;i++) { 32 divide=divide*10+(s[i]-'0'); 33 } 34 // cout<<divide<<endl; 35 // cout<<sub<<endl; 36 maxx-=sub/divide; 37 ans=max(ans,maxx); 38 } 39 printf("Case #%d: %lld ",cas++,ans); 40 } 41 }
J 巧妙的问题转化
HDU5942 Just a Math Problem
K 重叠区间直接减去，质数大于2个（区间长度大于777（from 百度数据范围内最远质数间隔）） 其余二分图匹配。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=2005; 4 int T,n,s,V,match[maxn],sleft,sright,nleft,nright; 5 vector<int> G[maxn]; 6 bool used[maxn]; 7 inline void addedge(int u,int v) { 8 G[u].push_back(v); 9 G[v].push_back(u); 10 } 11 bool dfs(int v) { 12 used[v]=true; 13 for (int i=0;i<(int)G[v].size();++i) { 14 int u=G[v][i],w=match[u]; 15 if (w<0||(!used[w]&&dfs(w))) { 16 match[v]=u; 17 match[u]=v; 18 return true; 19 } 20 } 21 return false; 22 } 23 inline int bipartite_matching() { 24 int res=0; 25 memset(match,-1,sizeof match); 26 for (int v=0;v<V;++v) 27 if (match[v]<0) { 28 memset(used,0,sizeof used); 29 if (dfs(v)) 30 ++res; 31 } 32 return res; 33 } 34 int main() 35 { 36 scanf("%d",&T); 37 for (int cas=1;cas<=T;++cas) { 38 scanf("%d%d",&n,&s); 39 sleft=max(n+1,s+1); 40 sright=s+1+n; 41 nleft=1; 42 nright=min(s,n); 43 if (nright-nleft>1000) 44 printf("Case #%d: No ",cas); 45 else { 46 V=nright-nleft+1; 47 for (int i=0;i<maxn;++i) 48 G[i].clear(); 49 for (int i=sleft;i<=sright;++i) 50 for (int j=nleft;j<=nright;++j) 51 if (i%j==0) 52 addedge(i-sleft,j-nleft+nright-nleft+1); 53 int sz=bipartite_matching(); 54 if (sz==nright-nleft+1) 55 printf("Case #%d: Yes ",cas); 56 else 57 printf("Case #%d: No ",cas); 58 } 59 } 60 return 0; 61 }