传送门:https://atcoder.jp/contests/abc192
A:
题意：现在有X枚硬币，要使硬币数为100的倍数还需要多少枚硬币（如果X已经为100的倍数不算）。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <int,int> pii; 16 int x; 17 int main(void) 18 { 19 cin>>x; 20 cout<<100*(x/100+1)-x<<endl; 21 return 0; 22 }
B:
题意：给定一个字符串，若奇数位上为小写字母，偶数位上为大写字母，输出Yes;否则输出No。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <int,int> pii; 16 string s; 17 int main(void) 18 { 19 cin>>s; 20 for(int i=0;i<s.size();i+=2) 21 { 22 if('a'<=s[i]&&s[i]<='z')continue; 23 cout<<"No"<<endl; 24 return 0; 25 } 26 for(int i=1;i<s.size();i+=2) 27 { 28 if('A'<=s[i]&&s[i]<='Z')continue; 29 cout<<"No"<<endl; 30 return 0; 31 } 32 cout<<"Yes"<<endl; 33 return 0; 34 }
C:
题意：设g1(x)为x降序重组得到的数，g2(x)为x升序重组得到的数，f(x)=g1(x)-g2(x)，给出N和K，求aK,其中a0=N,ai+1=f(ai)。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <int,int> pii; 16 string s; 17 int n,k; 18 int main(void) 19 { 20 cin>>n>>k; 21 while(k--&&n!=0) 22 { 23 s=to_string(n); 24 string s1=s,s2=s; 25 sort(s1.begin(),s1.end()); 26 sort(s2.rbegin(),s2.rend()); 27 int q=stoi(s2),p=stoi(s1); 28 n=q-p; 29 // cout<<s<<endl; 30 } 31 cout<<n<<endl; 32 return 0; 33 }
D:
题意：给定一串数字X和一个整数M，设d为X最大的数字，选择一个不小于d+1的整数n，将X看成n进制数，可以得到多少个不大于M的不同整数。
分析：首先特判一下，若X的位数为1，那无论进制是多少结果都是X，判断是否大于M即可；否则在不同进制下X必不相等，此时求出满足条件的最大的n，减去d即可。很容易想到用二分法。在判断的时候注意溢出。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <int,int> pii; 16 string s; 17 ll m; 18 int maxn,n; 19 bool check(ll mid) 20 { 21 ll sum=0,base=1; 22 for(int i=0;i<n;++i) 23 { 24 ll k=s[i]-'0'; 25 if(m/mid<sum)return false; 26 sum=sum*mid+k; 27 } 28 return sum<=m; 29 } 30 int main(void) 31 { 32 cin>>s; 33 cin>>m; 34 n=s.size(); 35 if(n==1) 36 { 37 if(s[0]-'0'>m)cout<<"0"<<endl; 38 else cout<<"1"<<endl; 39 return 0; 40 } 41 for(int i=0;i<n;++i) 42 { 43 if(s[i]-'0'>maxn)maxn=s[i]-'0'; 44 } 45 ll left=maxn,right=m+1; 46 while(right>left) 47 { 48 ll mid=(left+right+1)/2; 49 if(check(mid))left=mid; 50 else right=mid-1; 51 } 52 cout<<left-maxn<<endl; 53 return 0; 54 }
E:
题意：给定N个城市和M条道路，每条道路i到目的地需要的时间为Ti，发车的时间为Ki的倍数（包括0），求从X到Y城市需要的最短时间。
分析：设在当前城市已用时为t,可以知道此时从当前城市到其他城市的用时cost=t+Ki-d%Ki(若d%Ki==0,cost-=Ki),跑一边dijkstra即可。（注意pair里面的是long long）
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <ll,int> pii; 16 const ll INF=1e18; 17 const int maxn=1e6; 18 struct edge 19 { 20 int to; 21 ll t,k; 22 edge(int to,ll t,ll k):to(to),t(t),k(k){} 23 }; 24 vector<edge>e[maxn]; 25 ll dis[maxn]; 26 int n,m,x,y,vit[maxn]; 27 void dijkstra() 28 { 29 for(int i=1;i<=n;++i)dis[i]=INF; 30 priority_queue<pii,vector<pii>,greater<pii> >que; 31 dis[x]=0; 32 que.push({0,x}); 33 while(!que.empty()) 34 { 35 pii p=que.top(); 36 que.pop(); 37 ll d=p.first; 38 int u=p.second; 39 if(d>dis[u])continue; 40 for(int i=0;i<e[u].size();++i) 41 { 42 int v=e[u][i].to; 43 ll t=e[u][i].t,k=e[u][i].k; 44 ll cost=t+k-d%k; 45 if(d%k==0)cost-=k; 46 if(dis[v]>=d+cost) 47 { 48 dis[v]=d+cost; 49 que.push({dis[v],v}); 50 } 51 } 52 } 53 } 54 int main(void) 55 { 56 cin>>n>>m>>x>>y; 57 for(int i=1;i<=m;++i) 58 { 59 int a,b; 60 ll t,k; 61 cin>>a>>b>>t>>k; 62 edge e1(b,t,k); 63 edge e2(a,t,k); 64 e[a].push_back(e1); 65 e[b].push_back(e2); 66 } 67 dijkstra(); 68 if(dis[y]==INF)cout<<"-1"<<endl; 69 else cout<<dis[y]<<endl; 70 return 0; 71 }
F:
题意：给定N个数和需要得到的数X，选取k个数合并后这个数每次会增加k,求最少需要增加多少次，使得恰好得到X。
分析：问题转化为，当选取k个数时求最大的合并数max，使得(X-max)%k等于0（也就是说max和X同余），因此设dp[i][j][k]表示从前面i个数中选取k个数，使得合并数在模k后的余数为j的情况下的最大数，假设目前枚举到的选取个数为k,那么转移方程为:
(1):dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
(2):dp[i+1][(j+mod)%k][l+1]=max(dp[i+1][(j+mod)%k][l+1],dp[i][j][l]+a[i])
最终结果为min((x-dp[n][X%k][k])/k,1<=k<=n)
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cmath> 11 #include <set> 12 #include <cctype> 13 using namespace std; 14 typedef long long ll; 15 typedef pair <ll,int> pii; 16 const int maxn=101; 17 int n; 18 ll x; 19 ll a[maxn]; 20 ll dp[maxn][maxn][maxn]; 21 int main(void) 22 { 23 cin>>n>>x; 24 for(int i=0;i<n;++i)cin>>a[i]; 25 ll ans=x; 26 for(int k=1;k<=n;++k) 27 { 28 memset(dp,-1,sizeof(dp)); 29 dp[0][0][0]=0; 30 for(int i=0;i<n;++i) 31 { 32 ll mod=a[i]%k; 33 for(int j=0;j<k;++j) 34 { 35 for(int l=0;l<=k;++l) 36 { 37 if(dp[i][j][l]<0)continue; 38 dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]); 39 if(l<k) 40 { 41 dp[i+1][(j+mod)%k][l+1]=max(dp[i+1][(j+mod)%k][l+1],dp[i][j][l]+a[i]); 42 } 43 } 44 } 45 } 46 ll sum=dp[n][x%k][k]; 47 if(sum>0)ans=min(ans,(x-sum)/k); 48 } 49 cout<<ans<<endl; 50 return 0; 51 }