Codeforces Round #493 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 100005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n;
24 struct sair{
25     int v,pos;
26 }a[1005];
27 
28 bool cmp(sair a,sair b){
29     return a.v<b.v;
30 }
31 
32 int main(){
33     std::ios::sync_with_stdio(false);
34     cin>>n;
35     for(int i=1;i<=n;i++){
36         cin>>a[i].v;
37         a[i].pos=i;
38     }
39     if(n==1){
40         cout<<-1<<endl;
41         return 0;
42     }
43     sort(a+1,a+n+1,cmp);
44     if(n==2&&a[1].v==a[2].v) cout<<-1<<endl;
45     else{
46         cout<<n-1<<endl;
47         for(int i=2;i<=n;i++) cout<<a[i].pos<<" ";
48     }
49 }

View Code

B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 100005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n,m;
24 int a[105];
25 vector<int>ve;
26 
27 int main(){
28     std::ios::sync_with_stdio(false);
29     cin>>n>>m;
30     for(int i=1;i<=n;i++) cin>>a[i];
31     int ji=0,ou=0;
32     for(int i=1;i<=n;i++){
33         if(a[i]%2) ji++;
34         else ou++;
35         if(ji==ou&&ji!=0){
36             if(i!=n){
37                 ve.pb(abs(a[i]-a[i+1]));
38                 ji=0,ou=0;
39             }
40         }
41     }
42     sort(ve.begin(),ve.end());
43     int co=0;
44     for(auto i:ve){
45         if(i<=m){
46             co++;
47             m-=i;
48         }
49         else break;
50     }
51     cout<<co<<endl;
52 }

View Code

C

题意：有一个长度为n的01串，有两种操作，

1.将一个子串翻转，花费x

2.将一个子串中的0变成1，1变成0，花费 y

问把01串变成全1串的最小花费

思路：通过多次模拟可以发现一个规律（其实不用模拟，想一想就可以发现= =），每次翻转都会减少一串全0子串，所以贪心判断即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 100005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n;
24 ll x,y;
25 string str;
26 
27 int main(){
28     std::ios::sync_with_stdio(false);
29     cin>>n>>x>>y>>str;
30     int co=0;
31     int flag=0;
32     for(int i=0;i<str.length();i++){
33         if(str[i]=='0') flag=1;
34         else if(flag){
35             co++;
36             flag=0;
37         }
38     }
39     if(flag) co++;
40     if(!co) cout<<0;
41     else{
42         cout<<min((co-1)*x+y,co*y);
43     }
44 }

View Code

D

题意：罗马数字只有四个符号，分别代表1，5，10，50，问长度为n的罗马数字可以表示几种不同的十进制数

思路：通过打表可以发现，当n<=11时没有规律，当n>11时是公差为49的等差数列

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 100005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 ll a[]={0,4,10,20,35,56,83,116,155,198,244,292};
24 
25 
26 int main(){
27     std::ios::sync_with_stdio(false);
28     ll n;
29     cin>>n;
30     if(n<=11) cout<<a[n]<<endl;
31     else cout<<a[11]+49*(n-11);
32 }

View Code

E

题意：有一个

$思路：这题我只想到n^2的暴力，但显然过不了这题。。。无耻的去看了下题解，这篇写的很详细：https://www.luogu.org/blog/wcx/solution-cf997c$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 ll fac[maxn],inv[maxn];
24 
25 ll ksm(ll a,ll b){
26     ll ans=1;
27     a%=MOD;
28     while(b){
29         if(b&1){
30             ans=ans*a%MOD;
31         }
32         a=a*a%MOD;
33         b>>=1;
34     }
35     return ans;
36 }
37 
38 ll cal(ll x,ll y){
39     return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
40 }
41 
42 int main(){
43     std::ios::sync_with_stdio(false);
44     ll n;
45     cin>>n;
46     ll ans=0;
47     fac[0]=inv[0]=1;
48     for(int i=1;i<=n;i++){
49         fac[i]=fac[i-1]*i%MOD;
50         inv[i]=ksm(fac[i],MOD-2);
51     }
52     for(int i=1;i<=n;i++){
53         ans=(ans+ksm(3,(n*(n-i)+i))*ksm(-1,i+1)*cal(n,i)%MOD+MOD)%MOD;
54     }
55     ans=ans*2%MOD;
56     ll tmp=0;
57     for(int i=0;i<n;i++){
58         ll t=-ksm(3,i);
59         tmp=(tmp+cal(n, i)*ksm(-1, i+1)*(ksm(1 + t, n)-ksm(t, n)+MOD)%MOD+MOD)%MOD;
60     }
61     ans=(ans+tmp*3)%MOD;
62     cout<<ans<<endl;
63 }

View Code