传送门: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(abs(right-left)>1)
47 {
48 ll mid=(left+right)/2;
49 if(check(mid))left=mid;
50 else right=mid;
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即可。
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])
最终结果为max(dp[n][X%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 }