AtCoder Beginner Contest 192

传送门:https://atcoder.jp/contests/abc192

A:

题意：现在有X枚硬币，要使硬币数为100的倍数还需要多少枚硬币（如果X已经为100的倍数不算）。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
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;i2)
21     {
22         if('a'<=s[i]&&s[i]<='z')continue;
23         cout<<"No"<<endl;
24         return 0;
25     }
26     for(int i=1;i2)
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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
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<
30     }
31     cout<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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
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;ii)
23     {
24         ll k=s[i]-'0';
25         if(m/midreturn 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;ii)
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<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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
13 using namespace std;
14 typedef long long ll;
15 typedef pair 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 vectore[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,greater >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;ii)
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<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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <set>
12 #include 
13 using namespace std;
14 typedef long long ll;
15 typedef pair 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>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;ii)
31         {
32             ll mod=a[i]%k;
33             for(int j=0;jj)
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<endl;
50     return 0;
51 }
AtCoder

相关

codeforces和atcoder的思维题目

AtCoder Beginner Contest 218 个人题解

【AtCoder】AGC005 F - Many Easy Problems 排列组合+NTT

AtCoder Beginner Contest 193

AtCoder Beginner Contest 042 题解

AtCoder Regular Contest 133 题解 A - C

AtCoder Beginner Contest 238题解

AtCoder Beginner Contest 233

Atcoder Grand Contest 011&012

AtCoder Grand Contest 013&014

Atcoder 241

AtCoder Beginner Contest 243

标签