首页 > 代码库 > Codeforces Round #262 (Div. 2)

Codeforces Round #262 (Div. 2)

2024-07-18 16:27:24   230人阅读

A. Vasya and Socks

题意：起初给你n双袜子，每天穿一双，每到m天会多一双新的，求有多少天有袜子穿

题解：模拟即可

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 500+10013 #define maxm 500+10014 #define eps 1e-1015 #define ll long long16 using namespace std;17 inline int read()18 {19     int x=0,f=1;char ch=getchar();20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}21     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}22     return x*f;23 }24 25 int main()26 {27     int n=read(),m=read(),sum=n,i=0;28     while(1)29     {30         sum--;31         i++;if(i%m==0)sum++;32         if(!sum)break;    33     }34     cout<<i<<endl;35     return 0;36 }37
View Code

B. Little Dima and Equation

题意：求方程x=b*f(x)^a +c的处于（0，10^9)的解。其中f(x)=x的各位数字之和

题解：注意到f（x）确定以后，x唯一确定，只要枚举f(x)，检验得出的x的f（x）是否等于枚举的f(x)即可

         注意x的范围，以及输出是按递增序的（论不看全题目的危害性。。。）

代码： 

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 500+10013 #define maxm 500+10014 #define eps 1e-1015 #define ll long long16 using namespace std;17 inline int read()18 {19     int x=0,f=1;char ch=getchar();20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}21     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}22     return x*f;23 }24 int tot=0,d[1000];25 int main()26 {27     ll a=read(),b=read(),c=read();28     for(int i=1;i<=81;i++)29     {30       ll x=1,y=0;     31       for(int j=1;j<=a;j++)x=x*i;32       x=x*b+c;33       for(ll k=x;k;k/=10)y+=k%10;34       if(y==i&&x>0&&x<1000000000)d[++tot]=x;35       //cout<<x<<‘ ‘<<y<<endl;36     }37     sort(d+1,d+tot+1);38     cout<<tot<<endl;39     if(tot)40     {41         cout<<d[1];for(int i=2;i<=tot;i++)cout<<‘ ‘<<d[i];42     }43     return 0;44 }45
View Code

C. Present

题意：有n个数，你每次可以使一段连续的（<=w)的数都+1，有m次机会，求m次过后，最小值最大为多少？

题解：最小值最大一般为 二分，但是我没想到如何去判定一个数x能否达到。。。

UPD：看了标程，竟然是贪心。。。还在想线段树、单调队列的蒟蒻跪了。。。

         假设当前判断值为x

         从头往前扫，第一个不足x的肯定需要增加x-a[i]，那么肯定它作为连续的一段的最左边，那么把这一段的a[i]都加上x-a[i]，继续扫描第一个不足x的，就这么简单。。。

         我想如果我想到这个思路的话，肯定会去写个线段树+lazy来实现，而没有标程那么神，直接两个临时变量和一个临时数组搞定。

         tmp记录当前浇水次数，sum记录前i-m+1到i-1以这些为左端点浇水的次数，b数组维护的是一个前缀和使得该数组前 i 项之和为到 i 时的sum

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 20000013 #define maxm 500+10014 #define eps 1e-1015 #define ll long long16 using namespace std;17 inline int read()18 {19     int x=0,f=1;char ch=getchar();20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}21     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}22     return x*f;23 }24 int n,m,k,a[maxn],b[maxn];25 bool test(int x)26 {27     ll sum=0,tmp=0;28     memset(b,0,sizeof(b));29     for(int i=1;i<=n;i++)30     {31         sum+=b[i];32         if(sum+a[i]<x)33         {34             tmp+=x-(sum+a[i]);35             b[i+k]-=x-(sum+a[i]);36             sum+=x-(sum+a[i]);37         }38     }39     return tmp<=m;40 }41 int main()42 {43     freopen("input.txt","r",stdin);44     freopen("output.txt","w",stdout);45     n=read();m=read();k=read();46     for(int i=1;i<=n;i++)a[i]=read();47     int l=1,r=1100000000,mid;48     while(l<=r)49     {50         mid=(l+r)>>1;51         if(test(mid))l=mid+1;else r=mid-1;52     }53     printf("%d\n",r);54     return 0;55 }56
View Code

D题好像和最大异或有关？没看懂题，成对什么意思。。。

E题太神，没看题。。。

 


联系
我们