Lvat_s Blog

随便构造一下

#include<cstdio>
  
int main(){
freopen("2296.in","r",stdin);
freopen("2296.out","w",stdout);
long long a;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&a);
if(a==0){puts("-1");continue;}
printf("%lld\n",1234567890ll*1000000ll+a-(1234567890ll*1000000ll)%a);
}
return 0;
}

拓扑排序消圈+最大权闭合子图

因为每次僵尸都是从右往左走，那么我们对于右往左依次连边

然后每个点的攻击集合就是相当于选了攻击集合中的点就必须选择这个点。

那么我们反向建边，因为有可能出现循环保护的情况，所以先拓扑排序消圈然后按照最大权闭合子图的模型建网络流图即可。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

int en,en1,n,m,ok[1005],cur[1005],h[1005],h1[1005],score[1005],du[1005],level[1005],S,T,now,mxval;

struct Edge{
int b,f,next,back;
}e[1000005],e1[1000005];

int Cal(int x,int y){return (x-1)*m+y;}

void AddEdge1(int sa,int sb){
e1[++en1].b=sb;
e1[en1].next=h1[sa];
h1[sa]=en1;
du[sb]++;
}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(level[v] || !e[i].f)continue;
		Q.push(v);
		level[v]=level[u]+1;
	}
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
	if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(!f)return flow;
	}
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){
	for(int i=1;i<=T;i++)cur[i]=h[i];
	ans+=DFS(S,2100000000);
}
return ans;
}

void Toposort(){
queue<int> Q;
for(int i=1;i<=now;i++){
	if(!du[i]){ok[i]=1;Q.push(i);}
}
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h1[u];i;i=e1[i].next){
		int v=e1[i].b;
		du[v]--;
		if(!du[v]){ok[v]=1;Q.push(v);}
	}
}
}

int main(){
freopen("1565.in","r",stdin);
freopen("1565.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		int can;
		now++;
		scanf("%d %d",&score[now],&can);
        for(int k=1;k<=can;k++){
			int dx,dy;
			scanf("%d %d",&dx,&dy);
			dx++;dy++;
            AddEdge1(now,Cal(dx,dy));
        }
        if(j!=m)AddEdge1(now+1,now);
	}
}
Toposort();
S=now+1;T=now+2;
for(int i=1;i<=now;i++){
	if(ok[i]){
		if(score[i]>=0){AddEdge(S,i,score[i]);mxval+=score[i];}
		else AddEdge(i,T,-score[i]);
		for(int j=h1[i];j;j=e1[j].next){
			int v=e1[j].b;
			if(ok[v])AddEdge(v,i,2100000000);
		}
	}
}
printf("%d\n",mxval-Dinic());
return 0;
}

很久以前wzf出给我们的题目。。。

考虑加边，每次并查集加完只要并查集内联通就说明实际堵塞

不联通就说明实际联通

#include<cstdio>
   
int n,k,ans=1,f[10000005];
   
int Find(int x){
return x==f[x]?f[x]:f[x]=Find(f[x]);
}
   
void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}
   
int Get(int x,int y){
if(x==n || y==n || x==0 || y==0)return 0;
return (x-1)*n+y;
}
   
int main(){
freopen("4423.in","r",stdin);
freopen("4423.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n*n+n;i++)f[i]=i;
while(k--){
    int sa1,sb1,sa2,sb2;
    char w1[5],w2[5];
    scanf("%d %d %s %d %d %s",&sa1,&sb1,w1,&sa2,&sb2,w2);
    if(ans==0){sa1=sa2;sb1=sb2;w1[0]=w2[0];}
    if(w1[0]=='N'){
        if(Find(Get(sa1,sb1))!=Find(Get(sa1-1,sb1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1-1,sb1)));ans=1;}
        else ans=0;
    }
    else {
        if(Find(Get(sa1,sb1))!=Find(Get(sa1,sb1-1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1,sb1-1)));ans=1;}
        else ans=0;
    }
    if(ans)puts("TAK");
    else puts("NIE");
}
return 0;
}

sb题写挂还有资格参加省选？

写挂10+次，莫名RE，简直崩溃

最后选择了抄hzwer的代码

这题是一个裸的欧拉函数

把原题中的式子拆一下就行了

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,ans=0;

long long phiQ(long long x)
{
    long long t=x;
    for(long long i=2;i*i<=n;i++)
        if(x%i==0)
        {
            t=t/i*(i-1);
            while(x%i==0)x/=i;
        }
    if(x>1)t=t/x*(x-1);
    return t;
}

int main(){
freopen("2705.in","r",stdin);
freopen("2705.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i*i<=n;i++){
	if(n%i==0){
		ans+=(long long)i*phiQ(n/i);
		if(i*i<n)ans+=(long long)(n/i)*phiQ(i);
	}
}
printf("%lld\n",ans);
return 0;
}

二分判定,使用网络流

暴力重构图即可

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int n,m,k,en,h[705],level[705],S,T,cur[705],scr[255][255];

struct Edge{
int b,next,f,back;
}e[1000005];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int Bfs(){
queue<int> Q;
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(!e[i].f || level[v])continue;
		level[v]=level[u]+1;
		Q.push(v);
	}
}
return level[T];
}

int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
	if(e[i].f && level[v]==level[u]+1 && (fl=Dfs(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f==0)return flow;
	}
}
return flow-f;
}

int Dinic(){
int ans=0;
while(Bfs()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=Dfs(S,2100000000);}
return ans;
}

int Check(int score){
memset(h,0,sizeof(h));
en=0;
for(int i=1;i<=n;i++)AddEdge(S,i,1);
for(int i=1;i<=m;i++)AddEdge(i+n,T,1);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		if(scr[i][j]<=score)AddEdge(i,j+n,1);
	}
}
return Dinic()>n-k;
}

int main(){
freopen("4443.in","r",stdin);
freopen("4443.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		scanf("%d",&scr[i][j]);
	}
}
S=n+m+1;
T=n+m+2;
int l=1,r=100000000,ans=0;
while(l<=r){
	int mid=l+r>>1;
	if(Check(mid)){ans=mid;r=mid-1;}
	else {l=mid+1;}
}
printf("%d\n",ans);
return 0;
}

BZOJ 100AC啦！

我选择了这道题。

这题是一个裸的下界最小费用流

对于每条边(sa,sb)费用sc

可以连接S->sb,费用sc容量1表示至少走一次

sa->sb,费用sc,容量INF表示可以走多次

对于每个点i

可以连接i->T费用0容量nk表示可以从这里离开(此时已经看完了全部剧情)

i->1费用0容量INF表示可以在i号点退出游戏重新开始一局新游戏

看不懂请看代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,S,T,link[2005],h[2005],D[2005],flag[2005];

struct Edge{
int b,c,f,back,next;
}e[1000005];

void AddEdge(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int SPFA(){
queue<int> Q;
memset(D,127,sizeof(D));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && D[v]>D[u]+e[i].c){
			D[v]=D[u]+e[i].c;
			link[v]=i;
			if(!flag[v]){
				flag[v]=1;
				Q.push(v);
			}
		}
	}
}
return D[T]<2000000000;
}

int Cost(){
int Tow=link[T],flow=2100000000,cost=0;
while(Tow!=link[S]){
	flow=min(flow,e[Tow].f);
	Tow=link[e[e[Tow].back].b];
}
Tow=link[T];
while(Tow!=link[S]){
    e[Tow].f-=flow;
    e[e[Tow].back].f+=flow;
    cost+=flow*e[Tow].c;
    Tow=link[e[e[Tow].back].b];
}
return cost;
}

int Flow(){
int ans=0;
while(SPFA())ans+=Cost();
return ans;
}

int main(){
freopen("3876.in","r",stdin);
freopen("3876.out","w",stdout);
scanf("%d",&n);
S=n+1;T=n+2;
for(int i=1;i<=n;i++){
	int nk;
	scanf("%d",&nk);
	for(int j=1;j<=nk;j++){
		int sa,sb;
		scanf("%d %d",&sa,&sb);
		AddEdge(S,sa,1,sb);
		AddEdge(i,sa,2100000000,sb);
	}
	AddEdge(i,T,nk,0);
	if(i!=1)AddEdge(i,1,2100000000,0);
}
printf("%d\n",Flow());
return 0;
}

第二道莫比乌斯反演！

这题和HAOI2011的Problem b很像，但是改成了质数……

懒得写题解了:传送门

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int mu[10000005],g[10000005],T,n,m,pri[1000005],cnt,tab[10000005];

void Pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
	if(!tab[i]){g[i]=1;mu[i]=-1;pri[++cnt]=i;}
	for(int j=1;j<=cnt && pri[j]*i<=n;j++){
		tab[i*pri[j]]=1;
		if(i%pri[j]){mu[i*pri[j]]=-mu[i];g[i*pri[j]]=mu[i]-g[i];}
		else {mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;}
	}
}
for(int i=1;i<=n;i++)tab[i]=tab[i-1]+g[i];
}

long long Solve(long long n,long long m){
if(n>m)swap(n,m);
long long ans=0;
for(int i=1,last;i<=n;i=last+1){
	last=min(n/(n/i),m/(m/i));
	ans+=(n/i)*(m/i)*(tab[last]-tab[i-1]);
}
return ans;
}

int main(){
freopen("2820.in","r",stdin);
freopen("2820.out","w",stdout);
Pre(10000000);
scanf("%d",&T);
while(T--){
	scanf("%d %d",&n,&m);
	printf("%lld\n",Solve(n,m));
}
return 0;
}

老年颓废选手表示不能再颓了，毕竟2天没做题了虽然还是学习了一下后缀数组

第一道后缀数组！

裸题，因为后缀本来就排好序了，然后直接输出就行了

需要把串复制一遍

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

char s[200005];
int log2[200005],rmq[200005][20],n,sa[200005],rank[200005],rank2[200005],ws[200005],wv[200005],tot;

int cmp(int *r,int a,int b,int len){return (r[a]==r[b])&(r[a+len]==r[b+len]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,i=p=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

int main(){
freopen("1031.in","r",stdin);
freopen("1031.out","w",stdout);
scanf("%s",s);
n=strlen(s);
for(int i=n;i<2*n;i++)s[i]=s[i-n];
n*=2;
s[n]=0;
GetSA(s,sa,n+1,128);
for(int i=1;i<=n && tot<n/2;i++)if(sa[i]<n/2)printf("%c",s[sa[i]+n/2-1]),tot++;
return 0;
}

这题我居然挂了6次……简直是耻辱啊！

dead*4:二分上界打错

dead*1:二分判断条件打错

没救了……

好了，现在说一下题解

首先我们利用二分将其转化为判定[1,x]有多少个数不是完全平方数的正整数倍

------------------------以下为懒癌发作的Lvat_s复制的PoPoQQQ的题解

然后利用容斥原理，

容易发现每个乘积a前面的符号恰好是mu(a)

x以内i^2的倍数有[x/i^2]个,故有

这题和莫比乌斯反演没关系，算是莫比乌斯函数的一个应用吧。。。

-------------------------------------------------------------

详情请看代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

long long T,k,tab[1000005],prime[1000005],mu[1000005],cnt;

void Prepare(long long Num){
mu[1]=1;
for(long long i=2;i<=Num;i++){
	if(!tab[i]){
		prime[++cnt]=i;
		mu[i]=-1;
	}
	for(long long j=1;j<=cnt && i*prime[j]<=Num;j++){
		tab[i*prime[j]]=1;
		if(i%prime[j])mu[i*prime[j]]=-mu[i];
		else {mu[i*prime[j]]=0;break;}
	}
}
}

long long Test(long long x){
long long sq=(int)sqrt(x),ans=0;
for(long long i=1;i<=sq;i++){
	ans+=mu[i]*(x/(i*i));
}
return ans;
}

long long Solve(long long k){
long long l=1ll,r=10000000000ll,ans=210000000000000ll;
while(l<=r){
	long long mid=l+r>>1,tmp=Test(mid);
	if(tmp<k){l=mid+1;}
	else {ans=mid;r=mid-1;}
}
return ans;
}

int main(){
freopen("2440.in","r",stdin);
freopen("2440.out","w",stdout);
scanf("%lld",&T);
Prepare(1000000);
while(T--){
	scanf("%lld",&k);
	printf("%lld\n",Solve(k));
}
return 0;
}

这是今年的福建省选原题……按说不是很难但我却卡了很长时间……

我的写法十分诡异难以调试……以后得换一种写法了

题解直接抄一下懒得写了

------------------------------

------------------------------

我真的是严格按照这个题解写的！但是其他人的写法都和题解不一样……所以我很诧异……UPD:其实是一样的！只是细节有点区别！我真是太弱了！

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int n,siz,a[100005],b[100005],root[100005],bn,m;
vector<int> V[100005];

struct SegTree{
int nl,nr,l,r,sum,cre;
}tree[4000005];

void Add(int &rt,int lastrt,int l,int r,int pos,int val,int Rev){
if(Rev!=tree[rt].cre){rt=++siz;tree[rt].nl=tree[lastrt].nl;tree[rt].nr=tree[lastrt].nr;tree[rt].l=l;tree[rt].r=r;tree[rt].cre=Rev;}
if(l==r){tree[rt].sum+=val;return;}
int mid=l+r>>1;
if(pos<=mid)Add(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val,Rev);
if(pos>mid)Add(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val,Rev);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

int Sum(int rt,int l,int r){
if(rt==0)return 0;
if(l<=tree[rt].l && tree[rt].r<=r){
	return tree[rt].sum;
}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(tree[rt].nl,l,r);
if(r>mid)ans+=Sum(tree[rt].nr,l,r);
return ans;
}

int main(){
freopen("4408.in","r",stdin);
freopen("4408.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}
sort(b+1,b+n+1);
bn=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+bn+1,a[i])-b;V[a[i]].push_back(i);}
for(int i=1;i<=bn;i++){for(int j=0;j<V[i].size();j++)Add(root[i],root[i-1],1,n,V[i][j],b[a[V[i][j]]],i);}
scanf("%d",&m);
for(int i=1;i<=m;i++){
    int l,r;
	scanf("%d %d",&l,&r);
    int ans=0,tmp=-1;
    while(tmp<=ans){
		tmp=ans+1;
		ans=Sum(root[upper_bound(b+1,b+bn+1,tmp)-b-1],l,r);
    }
    printf("%d\n",ans+1);
}
return 0;
}