A：签到
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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 (k<y) ans=-1;else{if (y%2==0){if (k&1) ans+=k-2;else ans+=k;}else ans+=k-1;}}}cout<<ans<<endl;}return 0; }
C：大力数位dp。还可以把所有合法数都找出来然后二分找答案。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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<<calc(y)-calc(x-1)<<endl;}return 0; }
D：B题难度。双指针移动，若匹配上则ans++。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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 (x<m) ans=-1;cout<<ans;return 0; }
E：gcd一下求出线段上整点数量再暴力算交点去重即可。没有写，据说很卡精度。
F：可以发现所求的就是存在k>1，k∈N*使开k次方为整数的数。可以算出有多少个能开k次方的数，然后用莫比乌斯函数容斥。开方直接用pow再微调一下。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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\n",ans);}return 0; }
G：如果图是强连通的，那么图中每个点都在某些源到汇的路径上。于是只要源和汇之间相互可达就可以了。用这个性质直接随机的话据说错误率只有1e-8。
当然考虑靠谱的做法。注意到源汇的个数很少，考虑枚举源子集，验证其是否可能与剩下部分不在同一SCC内（当然枚举的子集不包括全集）。
源子集对应了一个汇子集。那么显然若汇子集大小不大于源子集，则可以将汇的出边全部连向该源子集，剩下部分无法与其强连通。
上述检验没有考虑子集内部是否可以连接至强连通。不过在枚举该子集的子集时这种情况已经被检验。
