Codeforces Round #450 (Div. 2)

时间：2023-11-22 13:33:44

Codeforces Round #450 (Div. 2)

http://codeforces.com/contest/900

A

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int a[];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     int n;

     cin>>n;

     int u,v;

     for(int i=;i<n;i++){

         cin>>u>>v;

         if(u>) a[]++;

         else a[]++;

     }

     if(a[]<=||a[]<=) cout<<"YES"<<endl;

     else cout<<"NO"<<endl;

 }

B

模拟除法

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int a[];

 ll fac[];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     int a,b,c;

     cin>>a>>b>>c;

     int co=;

     while(){

         a*=;

         int k=a/b;

         a%=b;

         if(k==c){

             cout<<co<<endl;

             return ;

         }

         co++;

         if(co>=) break;

     }

     cout<<-<<endl;

 }

C

找规律

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int n;

 int a[maxn],cnt[maxn];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     cin>>n;

     int max1=,max2=;

     for(int i=;i<=n;i++) cin>>a[i];

     for(int i=;i<=n;i++){

         if(a[i]>max1){

             max2=max1;

             max1=a[i];

             cnt[a[i]]--;

         }

         else if(a[i]>max2){

             cnt[max1]++;

             max2=a[i];

         }

     }

     int max3=-maxn,ans;

     for(int i=;i<=n;i++){

         if(cnt[i]>max3){

             max3=cnt[i];

             ans=i;

         }

     }

     cout<<ans<<endl;

 }

D

记忆化搜索+容斥

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int x,y;

 map<int,int>mp;

 ll pow_mul(ll a,ll b){

     ll ans=;

     while(b){

         if(b&) ans=(ans*a)%MOD;

         b>>=;

         a=(a*a)%MOD;

     }

     return ans;

 }

 ll dp(int x){

     if(x==) return ;

     if(mp.count(x)) return mp[x];

     mp[x]=pow_mul(,x-);

     for(int i=;i*i<=x;i++){

         if(x%i==){

             mp[x]=(mp[x]-dp(x/i)+MOD)%MOD;

             if(i!=x/i){

                 mp[x]=(mp[x]-dp(i)+MOD)%MOD;

             }

         }

     }

     return mp[x]=(mp[x]-dp()+MOD)%MOD;

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     cin>>x>>y;

     if(y%x){

         cout<<<<endl;

     }

     else{

         cout<<dp(y/x)<<endl;

     }

 }

E

DP

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 pii d[maxn];

 int f[][maxn], n, m, b[maxn];

 char a[maxn];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

      cin >> n;

     for (int i = ; i <= n; i++)

         cin >> a[i];

     cin >> m;

     for (int i = ; i <= n; i++)

     {

         if (a[i] == '?')

             b[i] = b[i-] + ;

         else b[i] = b[i-];

         if (a[i] != 'a')

             f[][i] = f[][i-]+;

         if (a[i] != 'b')

             f[][i] = f[][i-]+;

         if (f[!(m&)][i] >= m)

             d[i] = {d[i-m].first + , -(b[i]-b[i-m]-d[i-m].second)};

         d[i] = max(d[i-], d[i]);

     }

     cout << - d[n].second;

 }

相关文章