T1
首先不得不说，这道题虽然表面上看着算法很高深通常来说，这类题都需要(KMP),(AC)自动机，之类的。但是由于考试时间对于我来说并不是太多，所以我就直接莽了一下，直接暴力匹配，发现样例竟然一次过了。然后其实期望得分是(60~90 pts)，然而我没注意到两个(len)相乘会瞬见爆炸，然后就只得了(30 pts)。看完题解发现自己好笨，题解做法十分巧妙，将两个子串相加判断，因为当子串搜到了超出任意一个字串的长度时，那么长的那个字串的前(len1)位一定与短的字符串相同，如此计算，运算大大减小。很轻松就(A)了(发现我的朴素做法居然跑得最快，虽然空间也最大)。
Code
cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define scy(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout);
using namespace std;
const int maxn=2e5+7;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
char s[maxn],s1[maxn];
int a[maxn],a1[maxn];
int n;
int main() {
scy("string");
n=read();
for(int i=1; i<=n; i++) {
scanf("%s",s+1);
int len1=strlen(s+1);
scanf("%s",s1+1);
int len2=strlen(s1+1);
for(int i=1; i<=len1+len2; i++) {
if(i<=len1) a[i]=s[i]-'a';
a[i+len1]=s1[i]-'a';
}
for(int i=1; i<=len2+len1; i++) {
if(i<=len2) a1[i]=s1[i]-'a';
a1[i+len2]=s[i]-'a';
}
for(int i=1; i<=len1+len2; i++) {
if(i>len1) a[i]=a[i-len1];
if(i>len2) a1[i]=a1[i-len2];
if(a[i]>a1[i]) {
printf(">
");
break;
}
if(a[i]<a1[i]) {
printf("<
");
break;
}
if(i==len1+len2&&a[i]==a1[i]) {
printf("=
");
break;
}
}
}
return 0;
}
T2
当时考场上做(T2)的时候其实时间也就剩了(1)个小时，看了一眼别的题之后还是选择做这道题，经过思考后不难想到肯定跟根号的系数有关，与化简完后的根号内的数无多大关联。我当时马上就敲了一个快速幂，然后想枚举快速幂从大到小逼近(m)，然后如果m%qpow==0直接输出此时的i值，也就是系数。后来之后想到了跟组合数有关，但是考场没时间了，过了样例(可水了)，然后就交了，然后喜踢爆(0)，看完题解之后明白了咋写组合数，然后问题就迎刃而解了。但是我求系数的方法复杂度为(O(n)),而正解要求(O(sqrt n)),然后就只有(90 pts)。(交的时候又一次因为快速幂没模爆(0)了)。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
const int maxn = 1000000;
#define scy(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define int long long
const int mod=1e9+7;
using namespace std;
int fac[maxn];
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int qpow(int a,int b) {
int ret=1;
while(b) {
if(b&1) ret=ret*a;
a=a*a;
b=b/2;
}
return ret;
}
int C(int a, int b) {
if (a == 0 || a < b) {
return 0;
}
if (b == 0) {
return 1;
}
return fac[a] * qpow(fac[b], mod - 2) % mod * qpow(fac[a - b], mod - 2) % mod;
}
int n,m;
int n1=0,mi=0,sum;
signed main() {
scy("structure");
n=read(),m=read();
fac[0]=1;
for (int i = 1; i < maxn; ++i) {
fac[i] = 1ll * i * fac[i - 1] % mod;
}
while(mi<m) {
n1++;
mi=qpow(n1,2);
}
for(int i=n1-1; i>=1;i--) {
if(m%qpow(i,2)==0){
sum=i;
break;
}
}
printf("%lld
",C(sum+n-1,sum));
return 0;
}
对了这题(std)还锅了(简直就是某国集附体)。