链接:https://codeforces.com/contest/1295

 

A. Display The Number

贪心思路，尽可能放置更多位，如果n为奇数，消耗3去放置一个7，剩下的放1

 

AC代码:

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 int n,m;
 5 int main(){
 6     int t;
 7     cin>>t;
 8     while(t--){
 9         int n;
10         cin>>n;
11         string ans = "";
12         if(n%2 == 1) ans.append(1,'7'),ans.append((n-3)/2,'1'); 
13         else ans.append(n/2,'1');
14         cout<<ans<<endl; 
15     }
16     return 0;
17 }

 

B. Infinite Prefixes

 

前缀和思路，存字符串前n个位置的前缀和，如果cnt0+cnt1 = 0，且 x 在前缀和中出现过，那么就是无限的。

其他情况扫一遍字符串的前缀和，然后与x的差值和f[n]取余，如果为0，说明差值可以用任意个字符串的cnt0-cnt1拼接起来，ans就++

 

 1 #include<bits/stdc++.h>  
 2 using namespace std;
 3 typedef long long ll;
 4 int main(){
 5     int t;
 6     cin>>t;
 7     while(t--){
 8         int n,x;
 9         cin>>n>>x;
10         string s;
11         cin>>s;
12         int f[n+1];
13         f[0] = 0;
14         int can = 0;
15         for(int i = 0;i<n;i++){
16             if(f[i] == x) can = 1;
17             if(s[i] == '1') f[i+1] = f[i]-1;
18             else f[i+1] = f[i] + 1;
19         } 
20         if(f[n] == x) can = 1;
21         if(can == 1 && f[n] == 0) {
22             cout<<-1<<endl;
23             continue;
24         }
25         int ans = 0;
26         ll d = f[n];
27     //    cout<<d<<endl;
28         for(int i = 0;i<=n;i++){
29             if(f[i] == x) ans++;
30             if(i!=0 && f[i]<x && d>0 &&(x-f[i])%d==0) ans++;
31             if(i!=0 && f[i]>x && d<0 &&(f[i]-x)%(-d)==0) ans++;
32         }
33         cout<<ans<<endl; 
34     }
35     return 0;
36 }

 

 

C. Obtain The String

贪心思路，用一个next二维数组存储当前位置i 下一个26个字母的距离最近的位置，然后按需求跳转过去，如果找不到，那么需要的字串数量就+1，再从头开始扫描原串。

 

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const int maxn = 1e5+5;
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     while(n--){
10         string s,t;
11         cin>>s>>t;
12         int next[s.length()+1][26];
13         for(int i = 0;i<26;i++) next[s.length()][i] = -1;
14         for(int i = s.length()-1;i>=0;i--){
15             for(int j = 0;j<26;j++) next[i][j] = next[i+1][j];//存储i后面，26个字母距离i最近的位置
16             int cur = s[i]-'a';
17             next[i][cur] = i+1;
18         }
19         int ans = 1;
20         int cur = 0;
21         bool f = true;
22         for(int i = 0;i<t.length();i++){
23             int now = t[i]-'a';
24             if(next[cur][now]!=-1) cur = next[cur][now];//跳转过去
25             else{
26                 ans++;//如果找不的ans就++
27                 cur = 0;
28                 if(next[cur][now] == -1){//如果还没有，说明无法拼接起来
29                     f = false;
30                     break;
31                 }
32                 cur = next[cur][now];
33             }
34         }
35         if(!f) cout<<-1<<endl;
36         else cout<<ans<<endl;
37     }
38     return 0;
39 }

 

D. Same GCDs

设gcd（a，m）= n，那么找gcd（a +x ，m）= n个数，其实就等于找gcd（（a+x）/n，m/n) = 1的个数，等价于求m/n的欧拉函数

 

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 ll euler_phi(ll n) {
 5   ll m = ll(sqrt(n + 0.5));
 6   ll ans = n;
 7   for (ll i = 2; i <= m; i++)
 8     if (n % i == 0) {
 9       ans = ans / i * (i - 1);
10       while (n % i == 0) n /= i;
11     }
12   if (n > 1) ans = ans / n * (n - 1);
13   return ans;
14 }
15 ll gcd(ll a, ll b) {
16   if (b == 0) return a;
17   return gcd(b, a % b);
18 }
19 int main()
20 {
21     int t;
22     cin>>t;
23     while(t--){
24         ll a,m;
25         cin>>a>>m;
26         m=m/gcd(a,m);
27         ll x = euler_phi(m);
28         cout<<x<<endl;
29     } 
30     return 0;
31 }

 

E. Permutation Separation

建一颗线段树，叶子结点是花费从1到i所需要花费的前缀和，表示前i个元素全部移动到右边的花费，再维护区间最小值，然后从1到n-1扫一遍，对于第i个位置，找到数字i在序列中的位置 pos ，将区间1到pos-1加上数字i移动的花费，pos到n-1减去数字i移动的花费，因为位置大于等于i 的时候，不需要将数字i移动到右边，位置小于i 时，需要把数字i移动到左边，所以需要增加数字i的花费，结合线段树维护的是前缀和数组，那么对于每一个位置i 用线段树维护的最小值去更新答案ans即可。

 

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const int maxn = 2e5+5;
 5 ll pos[maxn],cost[maxn],a[maxn],sum[maxn];
 6 struct segT{
 7     ll l,r;
 8     ll dat,lz;
 9 }t[maxn*4];
10 void build(ll p,ll l,ll r){
11     t[p].l = l,t[p].r = r;
12     if(l == r) { t[p].dat = sum[l] ,t[p].lz = 0;return;}
13     ll mid = (l+r)/2;
14     build(p*2,l,mid);
15     build(p*2+1,mid+1,r);
16     t[p].dat = min(t[p*2].dat ,t[p*2+1].dat );
17 }
18 void upd(ll p,ll L,ll R,ll v){
19     if(t[p].l >= L&&t[p].r <= R ) {t[p].dat += v,t[p].lz +=v;return;}
20     if (t[p].lz && L!=R ) {
21     t[p * 2].dat += t[p].lz ,t[p*2+1].dat +=t[p].lz  ;
22     t[p * 2].lz  += t[p].lz ,t[p*2+1].lz += t[p].lz;  
23     t[p].lz = 0;                             
24     }
25     int mid = (t[p].l + t[p].r )/2;
26     if(L<=mid) upd(p*2,L,R,v);
27     if(R>mid) upd(p*2+1,L,R,v);
28     t[p].dat = min(t[p*2].dat ,t[p*2+1].dat );
29 }
30 int query(ll p,ll l,ll r){
31     if(l<=t[p].l && r>=t[p].r ) return t[p].dat ;
32     int mid = (t[p].l + t[p].r )/2;
33     int val = 0x3f3f3f3f;
34     if(l<=mid) val = min(val,query(p*2,l,r));
35     if(r>mid)  val = min(val,query(p*2+1,l,r));
36     return val;
37 }
38 int main()
39 {
40     int n;
41     scanf("%d",&n);
42     for(int i = 1;i<=n;i++) {
43         scanf("%lld",&a[i]);
44         pos[a[i]] = i;
45     }
46     for(int i = 1;i<=n;i++){
47         scanf("%lld",&cost[i]);
48         sum[i] = sum[i-1] + cost[i];
49     }
50     build(1,1,n-1);
51     ll ans = cost[n];
52     ans = min(ans,t[1].dat );//特判
53     for(int i = 1;i<=n;i++){
54         if(pos[i]!=n) upd(1,pos[i],n-1,-cost[pos[i]]);
55         if(pos[i]!=1) upd(1,1,pos[i]-1,cost[pos[i]]);
56         ans = min(ans,t[1].dat);
57     }
58     printf("%lld",ans);
59     return 0;
60 }