链接: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 }