Codeforces Round #491 (Div. 2)

2022-10-30 11:20:10

Codeforces Round #491 (Div. 2)

https://codeforces.com/contest/991

A

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int main(){

     std::ios::sync_with_stdio(false);

     int a,b,c,n;

     cin>>a>>b>>c>>n;

     int ans=n-a-b+c;

     if(ans>&&a<n&&b<n&&c<n&&n-ans>=a&&n-ans>=b&&n-ans>=c&&c<=a&&c<=b&&ans<=n) cout<<ans<<endl;

     else cout<<-<<endl;

 }

B

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 int a[];

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     ll sum=;

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

         cin>>a[i];

         sum+=a[i];

     }

     sort(a+,a+n+);

     if(round(sum*1.0/n)==){

         cout<<<<endl;

         return ;

     }

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

         sum+=-a[i];

         if(round(sum*1.0/n)==){

             cout<<i<<endl;

             break;

         }

     }

 }

C

题意：a有n个糖果，在开始的时候 a 选择一个整数k，表示他每天会吃k个糖果，b也想吃糖果，他每天会吃当前数量的10%(下取整)的糖果,a先开始吃，问a选择的k值最小为多少，使得他吃的糖果的数量大于等于总数的一半。

思路：二分最小值即可。注意：取10%的时候要用tmp/10,不能用tmp*0.1,会有精度问题（被坑了好久）

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 ll n;

 bool Check(ll mid){

     ll sum1=,sum2=;

     ll tmp=n;

     ll t;

     while(tmp){

         if(tmp>=mid){

             tmp-=mid;

             sum1+=mid;

         }

         else {

             sum1+=tmp;

             tmp=;

         }

         if(tmp>=){

             t=tmp/;

             sum2+=t;

             tmp-=t;

         }

     }

     if(sum1>=sum2) return true;

     return false;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     ll L=,R=n,mid;

     while(L<=R){

         mid=L+R>>;

         if(Check(mid)){

             R=mid-;

         }

         else{

             L=mid+;

         }

     }

     cout<<L<<endl;

 }

D

题意：给定宽为两行的矩阵，问能放多少木块。

思路：因为只有两行，所以直接贪心即可，把每列有空的地方能放则放，要注意，当第一列遍历到i位置时，第二列i-1位置是否为空

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int book[][];

 int len;

 string s1,s2;

 bool Check(int x){

     if(x->=){

         if(!book[][x]&&!book[][x-]&&!book[][x]&&s1[x]==''&&s2[x-]==''&&s2[x]==''){

             book[][x]=;book[][x-]=;book[][x]=;

             return true;

         }

     }

     if(x+<len){

         if(!book[][x]&&!book[][x+]&&!book[][x]&&s1[x]==''&&s2[x+]==''&&s2[x]==''){

             book[][x]=;book[][x+]=;book[][x]=;

             return true;

         }

         if(!book[][x]&&!book[][x+]&&!book[][x+]&&s1[x]==''&&s1[x+]==''&&s2[x+]==''){

             book[][x]=;book[][x+]=;book[][x+]=;

             return true;

         }

         if(!book[][x]&&!book[][x+]&&!book[][x]&&s1[x]==''&&s1[x+]==''&&s2[x]==''){

             book[][x]=;book[][x+]=;book[][x]=;

             return true;

         }

     }

     return false;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>s1>>s2;

     len=s1.length();

     int ans=;

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

         if(!book[][i]){

             if(Check(i)){

                 ans++;

             }

         }

     }

     cout<<ans<<endl;

 }

E

题意：给你一个数字序列A（长度不超过18位），问有多少个序列B满足：

1、A中所有数字都一定要在B中出现过；

2、B中所有数字也一定要在A中出现过；

3、序列B不能以0开头

比如：如果看到数字2028，它可能实际的车号可能是2028,8022,2820或者是820。 而80号、22208号、52号肯定不是这辆车的号码。 而且，实际的车号不能以数字0开头，例如，数字082不能也是实际的车号。 给定看到的数字n，求出所有可能的车号种数。

思路：枚举各个位上出现的数的个数。先不考虑前导0的情况下，车号总数为：车号位数之和的阶乘除以各个位数的个数。然后在减去前导0的情况即可

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int num[];

 ll fac[];

 ll sum[];

 ll ans;

 void dfs(int pos){

     if(pos==){

         ll co=;

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

             co+=sum[i];

         }

         ll tmp=fac[co];

         for(int i=;i<;i++) tmp/=fac[sum[i]];

         if(sum[]>=) tmp-=(tmp*sum[]/co);

         ans+=tmp;

         return;

     }

     for(int i=;i<=num[pos];i++){

         sum[pos]=i;

         dfs(pos+);

     }

     if(num[pos]==) dfs(pos+);

 }

 int main(){

     std::ios::sync_with_stdio(false);

     string str;

     fac[]=;

     for(int i=;i<;i++) fac[i]=fac[i-]*i;

     cin>>str;

     for(int i=;i<str.length();i++){

         num[str[i]-'']++;

     }

     dfs();

     cout<<ans<<endl;

 }

F

题意：给定n,把n简短化，比如：2000000000变成2*10^9，注意，不能使用括号，不能有2^3^4这样的形式

思路：先预处理出满足条件的a^b的形式，然后枚举这样的式子，在需要的情况下添加‘*’和‘+’，贪心判断长度即可

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

 #define IT set<ll>::iterator

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 1000006

 #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<ll,ll>pll;

 typedef pair<ll,int> pli;

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

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 map<ll,string>mp;

 int main(){

     std::ios::sync_with_stdio(false);

     ll n;

     cin>>n;

     ll nn=sqrt(n);

     string tmp;

     for(ll i=;i<=nn;i++){

         ll num=i*i;

         int co=;

         while(num<=n){

             tmp=to_string(i)+"^"+to_string(co);

             if(!mp.count(num)) mp[num]=to_string(num);

             if(mp[num].size()>tmp.size()) mp[num]=tmp;

             co++;

             num*=i;

         }

     }

     string ans=to_string(n);

     map<ll,string>::iterator it;

     for(it=mp.begin();it!=mp.end();it++){

         tmp="";

         ll a=n/it->first,b=n%it->first;

         if(a>){

             if(mp.count(a)) tmp=mp[a];

             else tmp=to_string(a);

             tmp+="*";

         }

         tmp+=it->second;

         if(b) tmp=tmp+"+"+(mp.count(b)?mp[b]:to_string(b));

         if(ans.size()>tmp.size()) ans=tmp;

     }

     cout<<ans<<endl;

 }
上一篇：Android Studio导入项目


下一篇：解决java.lang.NoClassDefFoundError: org/aopalliance/intercept/MethodInterceptor问题