Codeforces ECR50 div2题解

　　A：签到

#include 
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
ll read()
{ll x=0,f=1;char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
ll n,k;
int main()
{n=read(),k=read();cout<<(k-1)/n+1;return 0;
}

　　B：大讨论。想清楚的话可以写的更优美一点。

#include 
#include
#include
#include
#include
#include
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n;
int main()
{n=read();for (int i=1;i<=n;i++){long long x,y,k,ans=-1;cin>>x>>y>>k;if (x>y) swap(x,y);if (k>=x){if (x==y) ans=((k&1)==(x&1))?k:k-2;else{ans=x;k-=x;y-=x;if (k1;else{if (y%2==0){if (k&1) ans+=k-2;else ans+=k;}else ans+=k-1;}}}cout<endl;}return 0;
}

　　C：大力数位dp。还可以把所有合法数都找出来然后二分找答案。

#include 
#include
#include
#include
#include
#include
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,a[20];
long long C(int n,int m)
{if (m<0) return 0;if (m==0) return 1;if (m==1) return n;if (m==2) return n*(n-1)/2;if (m==3) return n*(n-1)*(n-2)/6;
}
long long calc(long long x)
{int n=0,cnt=0;long long ans=0;memset(a,0,sizeof(a));while (x) a[++n]=x%10,x/=10;for (int i=n;i;i--)if (a[i]){if (cnt<=3) ans++;if (cnt<=2) ans+=9*C(i-1,1);if (cnt<=1) ans+=9*9*C(i-1,2);if (cnt<=0) ans+=9*9*9*C(i-1,3);cnt++;if (cnt<=3) ans+=a[i]-1;if (cnt<=2) ans+=(a[i]-1)*9*C(i-1,1);if (cnt<=1) ans+=(a[i]-1)*9*9*C(i-1,2);}if (cnt<=3) ans++;return ans;
}
int main()
{n=read();for (int i=1;i<=n;i++){long long x,y;cin>>x>>y;cout<1)<<endl;}return 0;
}

　　D：B题难度。双指针移动，若匹配上则ans++。

#include 
#include
#include
#include
#include
#include
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
#define N 300010
int n,m,ans=0;
long long a[N],b[N];
int main()
{n=read();for (int i=1;i<=n;i++) a[i]=read()+a[i-1];m=read();for (int i=1;i<=m;i++) b[i]=read()+b[i-1];int x=0;for (int i=1;i<=n;i++){while (x<=m&&a[i]>b[x]) x++;if (x>m) {ans=-1;break;}if (a[i]==b[x]) ans++;}if (a[n]!=b[m]) ans=-1;if (x1;cout<<ans;return 0;
}

　　E：gcd一下求出线段上整点数量再暴力算交点去重即可。没有写，据说很卡精度。

　　F：可以发现所求的就是存在k>1，k∈N*使开k次方为整数的数。可以算出有多少个能开k次方的数，然后用莫比乌斯函数容斥。开方直接用pow再微调一下。

#include 
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
ll read()
{ll x=0,f=1;char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
#define N 110
int T,prime[N],mobius[N],cnt=0;
bool flag[N];
ll calc(ll n,int k)
{ll a=pow(n,(long double)1/k);ll s=1;for (int i=1;i<=k;i++){if (s>n/(a+1)) break;s=s*(a+1);if (i==k&&s<=n) return a+1;}return a;
}
int main()
{flag[1]=1;mobius[1]=1;for (int i=2;i<=100;i++){if (!flag[i]) prime[++cnt]=i,mobius[i]=-1;for (int j=1;prime[j]*i<=100&&j<=cnt;j++){flag[prime[j]*i]=1;if (i%prime[j]==0) break;mobius[prime[j]*i]=-mobius[i];}}T=read();while (T--){ll n=read(),ans=0;for (int i=1;i<=60;i++)if (mobius[i]) ans+=mobius[i]*(calc(n,i)-1);printf("%I64d
",ans);}return 0;
}

　　G：如果图是强连通的，那么图中每个点都在某些源到汇的路径上。于是只要源和汇之间相互可达就可以了。用这个性质直接随机的话据说错误率只有1e-8。

　　当然考虑靠谱的做法。注意到源汇的个数很少，考虑枚举源子集，验证其是否可能与剩下部分不在同一SCC内（当然枚举的子集不包括全集）。

　　源子集对应了一个汇子集。那么显然若汇子集大小不大于源子集，则可以将汇的出边全部连向该源子集，剩下部分无法与其强连通。

　　上述检验没有考虑子集内部是否可以连接至强连通。不过在枚举该子集的子集时这种情况已经被检验。