一些相互无关联的题目的集合
都是码量不大,略有思维难度的题 做起来还是很舒适的
空间限制很小,不足以存下整个字符串,故暴力判断不可行。
考虑使用字符串哈希算法,判断原串和反串的哈希值是否相等。
设原串第 \(i\) 个字符的哈希值为 \(S_i\) ,反转串的第 \(i\) 个字符哈希值为 \(S'_i\) ,其中 \(i>0\)
哈希参数为 \(b=…,p=2^{64}\) ,字符串前 \(k\) 位的哈希值为 \(hash(k)\)
对于原串,\(hash(k)=(hash(k-1)\times b+S_k)\bmod p\)
对于反转串,\(hash(k)=(hash(k-1)+S_k\times b^{k-1})\bmod p\)
#include<cstdio>
#define gc getchar()
typedef unsigned long long ull; //利用ull的自然溢出
const ull b=1919; ull s1,s2,t=1,a;
int main() {
char c=gc; while (c>'z'||c<'a') c=gc;
while (c>='a'&&c<='z')
s1=s1*b+(a=c-'a'),s2+=t*a,t*=b,c=gc;
puts(s1==s2?"TAK":"NIE");
return 0;
}
线性筛板子题。直接上代码。
#include<cstdio>
#include<bitset>
const int N=100000000; int cnt,p[5800000];
std::bitset<N+10>v;
int main() {
for (int i=2; i<=N; ++i) { //筛
v[i]||(p[++cnt]=i);
for (int j=1; j<=cnt&&1ll*i*p[j]<=N; ++j) {
v[i*p[j]]=1;
if (i%p[j]==0) break;
}
}
for (int i=1; i<=cnt; i+=100) //输出
printf("%d\n",p[i]);
return 0;
}
题目要求的是 \(K^x\equiv 1\pmod M\) 的最小正整数解,如果无解则输出 Let's go Blue Jays!
发现 \((K,M)>1\) 时必然无解(必有 \((K,M)\mid K^x\bmod M\)),否则必然有解。
所以我们先判一下无解。如果有解,这时 \(K,M\) 互质,可直接使用BSGS解决。
代码使用的是手写哈希的方法
#include<cstdio>
#include<cmath>
#define rep(i) for (int i=1; i<=m; ++i)
const int P=10003; int p,a,m,t,s=1,S=1,cnt,last[P];
struct node { int i,x,pre; }E[50000];
int gcd(int x,int y) { return y?gcd(y,x%y):x; }
inline void add(int i,int x) { E[++cnt]={i,x,last[t=i%P]},last[t]=cnt; } //插入
inline int find(int i) { //查找
for (int j=last[i%P]; j; j=E[j].pre) if (E[j].i==i) return E[j].x;
return -1;
}
int main() {
scanf("%d%d",&p,&a); m=ceil(sqrt(p));
if (gcd(p,a)>1) return puts("Let's go Blue Jays!"),0; //判无解
add(1,0); rep(j) s=1ll*s*a%p,add(s,j);
rep(i) if (~(t=find(S=1ll*S*s%p)))
if (i*m-t) return printf("%d\n",i*m-t),0;
return 0;
}
题意:你tm不能点链接进去看吗
容易发现:
当左上角确定时,符合条件的矩形最多只有1个。
我们处理一个数组 \(s_{x,y}\) ,表示以 \((x,y)\) 为左上角的logo的最大边长(不存在则为0)。
易知无需特意求最大值,只要存在就一定是最大的。
对于询问,考虑二分答案,我们要实现的功能是判断一个子矩阵内有没有边长不小于常数 \(a\) 的logo。
“不小于”显然不好处理。这里再给出一个有用的性质:
在这个子矩阵内如果存在边长大于 \(a\) 的logo,那一定有边长等于 \(a\) 的logo。
因为将大logo的外圈去掉一定可以得到任意比它小的logo。
问题转化为:给出 \(a\) 和一个子矩阵,判断该子矩阵内是否存在 \(s_{x,y}=a\) 。
这个问题比较simple,可以对每种 \(s_{x,y}\) 分别处理二维前缀和 \(f[s_{x,y}][1\sim n][1\sim m]\),就可以实现 \(O(1)\) 查询。
这里补充一下 \(s\) 数组的处理方法
我们对4种颜色各预处理出二维前缀和,这样我们就能够 \(O(1)\) 查询某个矩形是否只包含某种颜色。
这样,只要给出了左上角坐标和边长,我们就可以 \(O(1)\) 判断这个矩形能不能做logo。
这样一来,我们就有了 \(O(n^3)\) 的算法。(这里假设 \(n,m\) 同级)
实现时其实我们不需要存 \(s\) ,只需要把 \(f\) 存下来就行了。详见代码
时间复杂度: \(O(n^3+q \log n)\) (仍然假设 \(n,m\) 同级)
虽然说要处理4种颜色的前缀和,但颜色这维没必要开到4。
这样只利用了正数,我们可以把负数也利用起来,可以压掉一半空间,也不会出错 典型的闲得没事干
#include<stdio.h>
#include<ctype.h>
#define rep(i,x) for (int i=1; i<=x; ++i)
#define gc (l==r&&(r=(l=c)+fread(c,1,1<<21,stdin),l==r)?EOF:*l++)
const int NN=502; int n,m,q,x1,y1,x2,y2,t=1,a1,a2,p=-1,p1;
int num[10],s1[NN][NN],s2[NN][NN],f[NN>>1][NN][NN];
char ch[NN],c[1<<21],cw[1<<21],*l=c,*r=c;
inline int read() { //fread快读
int x=0; char ch=gc;
while (!isdigit(ch)) ch=gc;
while (isdigit(ch)) x=x*10+(ch^48),ch=gc;
return x;
}
inline void write(int x) { //fwrite快输
do { num[++p1]=x%10; }while (x/=10);
do { cw[++p]=num[p1]^48; }while (--p1);
cw[++p]='\n';
}
inline int F(int x) { //计算子矩阵内是否存在边长为x的logo
int a=x2-x-x+1,b=y2-x-x+1;
return f[x][a][b]-f[x][x1][b]-f[x][a][y1]+f[x][x1][y1];
}
inline int min(int x,int y) { return x<y?x:y; }
inline int S1(int x1,int y1,int x2,int y2) {
return s1[x2][y2]-s1[x1][y2]-s1[x2][y1]+s1[x1][y1];
}
inline int S2(int x1,int y1,int x2,int y2) {
return s2[x2][y2]-s2[x1][y2]-s2[x2][y1]+s2[x1][y1];
}
int main() {
scanf("%d%d%d",&n,&m,&q);
rep(i,n) {
scanf("%s",ch+1);
rep(j,m) {
a1=0,ch[j]=='R'&&(a1=1),ch[j]=='G'&&(a1=-1); // 对R&G进行压缩
a2=0,ch[j]=='Y'&&(a2=1),ch[j]=='B'&&(a2=-1); // 对Y&B进行压缩
s1[i][j]=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1]+a1;
s2[i][j]=s2[i-1][j]+s2[i][j-1]-s2[i-1][j-1]+a2;
}
}
rep(i,n) rep(j,m) { //枚举左上角
for (int k=min(n-i+1,m-j+1)>>1; k; --k) { //枚举边长的一半
int i1=i-1,j1=j-1,i2=i1+k,j2=j1+k,i3=i2+k,j3=j2+k,S=k*k;
int *t=&f[k][i][j]; *t=*(t-NN)+*(t-1)-*(t-NN-1);
S1(i1,j1,i2,j2)==S&&S1(i1,j2,i2,j3)==-S&&
S2(i2,j1,i3,j2)==S&&S2(i2,j2,i3,j3)==-S&&(++*t);
}
}
for ( ; q; --q) {
x1=read(),y1=read(),x2=read(),y2=read(),--x1,--y1;
int l=0,r=min(x2-x1,y2-y1)>>1;
while (l+1<r) F(t=l+r>>1)||(!t)?l=t:r=t;
F(r)||(r=l),write(r*r<<2); //我正常二分答案总是出锅 所以写成这样了
}
return fwrite(cw,1,p+1,stdout),0;
}
关于这份代码为什么疯狂卡常:洛谷上显示的用时似乎是比CF原数据大一些,然后我想把这个总用时卡进10s
交了一面之后以10.12s的成绩放弃了 而且只有第六优解 我自闭了
看到题感觉是BSGS,而 \(X\) 的递推式多了个常数 \(b\) ,所以要想办法把常数项弄掉
\(X_{i+1}\equiv aX_i+b \pmod p\)
设 \(X_{i+1}+x\equiv a(X_i+x)\pmod p\)
易得 \(x=\dfrac b{a-1}\) 。这个显然可以算出来,下文为了方便还是用 \(x\)
那么 \(X_{i+1}+x\equiv a(X_i+x)\pmod p\)
所以 \(X_n+x\equiv a^{n-1}(X_1+x)\pmod p\)
题目问的是满足 \(X_n=t\) 的 \(n\) 的最小值
可以推出式子: \(a^{n-1}\equiv\dfrac{t+x}{X1+x}\pmod p\)
这就是个BSGS板子了
注意求出 \(n-1\) 后还要+1,这时不需要再次膜 \(p\)
然后是一些特殊情况
\(X_1=t\) 直接输出1
\(a=0\) 当 \(b=t\) 时输出2
,否则无解
\(a=1\) 这种情况下 \(X\) 是个等差数列,简单计算易得答案 \(n=((t-X_1)\times inv(b,p)\bmod p)+1\)
(这里也是+1后不取模)
代码中在一些求逆元的方法要判一下是否无解 然后就没什么了
#include<stdio.h>
#include<string.h>
#include<math.h>
const int P=10003; int T,m,p,a,b,x1,t,tt,s,S,cnt,last[P];
struct node { int i,x,pre; }E[50000];
inline int _power(int x,int y) {
int s=1;
while (y) (y&1)&&(s=1ll*s*x%p),x=1ll*x*x%p,y>>=1;
return s;
}
inline int inv(int x) { return _power(x,p-2); }
inline void add(int i,int x) { E[++cnt]={i,x,last[tt=i%P]},last[tt]=cnt; }
inline int find(int i) {
for (int j=last[i%P]; j; j=E[j].pre) if (E[j].i==i) return E[j].x;
return -1;
}
void solve() {
cnt=0,memset(last,0,sizeof last);
scanf("%d%d%d%d%d",&p,&a,&b,&x1,&t);
if (x1==t) { puts("1"); return ; } //x1=t
if (!a) { puts(b==t?"2":"-1"); return ; } //a=0
if (a==1) { //a=1
if (!b) { puts("-1"); return ; } ((t-=x1)%=p)<0&&(t+=p);
printf("%d\n",1ll*t*inv(b)%p+1); return ;
}
b=1ll*b*inv(a-1)%p; if (x1+b==p) { puts("-1"); return ; } //不存在逆元
s=b=1ll*(t+b)*inv(x1+b)%p,m=ceil(sqrt(p)); //以下为BSGS
for (int i=0; i<=m; ++i) add(s,i),s=1ll*s*a%p; s=_power(a,m),S=1;
for (int i=1; i<=m; ++i) if (~(tt=find(S=1ll*S*s%p)))
{ printf("%d\n",i*m-tt+1); return ; }
puts("-1");
}
int main() {
for (scanf("%d",&T); T; --T) solve();
return 0;
}
和[NOI2001]食物链差不多,都是种类并查集模板题
开三倍空间存本身、食物、天敌
多组数据没啥名堂
#include<stdio.h>
#include<ctype.h>
int n,m,k,n3,ans,x,x1,x2,y,y1,y2,f[150010];
inline int read() {
int x=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x;
}
int find(int x) { return f[x]==x?x:(f[x]=find(f[x])); } //路径压缩
int main() {
for (int T=read(); T; --T) {
n=read(),m=read(),n3=n*3,ans=0; //ans表示假话总数
for (int i=1; i<=n3; ++i) f[i]=i;
for ( ; m; --m) {
k=read(),x=read(),y=read();
if (x>n||y>n) { ++ans; continue; }
x1=find(x+n),x2=find(x+n+n),x=find(x); // 食物&天敌&本身
y1=find(y+n),y2=find(y+n+n),y=find(y); // 食物&天敌&本身
k==1?
x==y1||x1==y?++ans:(f[x]=y,f[x1]=y1,f[x2]=y2): //同类
x==y||x==y1?++ans:(f[x]=y2,f[x1]=y,f[x2]=y1); //x吃y
}
printf("%d\n",ans);
}
return 0;
}
题意:求 \(\sum\limits_{x=1}^n\sum\limits_{y=1}^x[(x,y)>1]\)
不要看到这种式子就上莫反,这题用 \(O(T\sqrt n)\) 的算法几乎不可能过
后面那个求和其实就是 \(x-\varphi(x)\) 。
线性筛处理欧拉函数,然后算 \(x-\varphi(x)\) 的前缀和,就可以 \(O(1)\) 询问了。
时间复杂度 \(O(T+N)\) 。
#include<stdio.h>
#include<ctype.h>
const int N=100000; int n,cnt,T,t,p[10000];
int v[N+2],phi[N+2]; long long s[N+2];
void prework() {
for (int i=2; i<=N; ++i) { //线性筛板子
v[i]||(p[++cnt]=i,phi[i]=i-1);
for (int j=1; j<=cnt&&1ll*p[j]*i<=N; ++j) {
v[t=i*p[j]]=1;
if (i%p[j]==0) { phi[t]=p[j]*phi[i]; break; }
phi[t]=phi[i]*(p[j]-1);
}
s[i]=s[i-1]+i-phi[i]; //处理前缀和
}
}
inline int read() { //简易快读
int x=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x;
}
int main() {
prework(),T=read();
for (int i=1; i<=T; ++i)
printf("Case %d: %lld\n",i,s[read()]);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章