作者：血玉残阳 | 来源：互联网 | 2023-08-31 14:09
感觉CQOI的难度挺好的，比较贴近自身，所以拿出来做了一下CQOI2016Day1T1:不同的最小割涉及算法:最小割分治最小割树思路:最小割树裸题,直接分治最小割,记录下答案
感觉CQOI的难度挺好的，比较贴近自身，所以拿出来做了一下
CQOI2016 Day1 T1:不同的最小割
涉及算法:最小割/分治/最小割树
思路:
最小割树裸题,直接分治最小割,记录下答案,最后排序一下,统计不同的答案即可
CODE:
#include
#include
#include
#include
#include
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define maxn 1000
#define maxm 100010
int n,m,q,t,ans[maxn],tot,id[maxn],tmp[maxn];
struct Edgenode{int next,to,cap;}edge[maxm];
int head[maxn],cnt=1;
void add(int u,int v,int w)
{cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].cap=w;}
void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);}
int dis[maxn],que[maxn<<1],cur[maxn],S,T;
bool bfs()
{
memset(dis,-1,sizeof(dis));
que[0]=S; dis[S]=0; int he=0,ta=1;
while (he<ta)
{
int now=que[he++];
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==-1)
dis[edge[i].to]=dis[now]+1,que[ta++]=edge[i].to;
}
return dis[T]!=-1;
}
int dfs(int loc,int low)
{
if (loc==T) return low;
int w,used=0;
for (int i=cur[loc]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==dis[loc]+1)
{
w=dfs(edge[i].to,min(low-used,edge[i].cap));
edge[i].cap-=w; edge[i^1].cap+=w;
used+=w; if (edge[i].cap) cur[loc]=i;
if (used==low) return low;
}
if (!used) dis[loc]=-1;
return used;
}
#define inf 0x7fffffff
int dinic()
{
int tmp=0;
while (bfs())
{
for (int i=1; i<=n; i++) cur[i]=head[i];
tmp+=dfs(S,inf);
}
return tmp;
}
void init()
{
cnt=1;
memset(ans,0,sizeof(ans));
memset(head,0,sizeof(head));
}
bool visit[maxn];
void DFS(int x)
{
visit[x]=1;
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].cap && !visit[edge[i].to])
DFS(edge[i].to);
}
void work(int L,int R)
{
if (L==R) return;
for (int i=2; i<=cnt; i+=2)
edge[i].cap=edge[i^1].cap=(edge[i].cap+edge[i^1].cap)>>1;
S=id[L],T=id[R];
int maxflow=dinic();
memset(visit,0,sizeof(visit)); DFS(S);
// for (int i=1; i<=n; i++) if (visit[i])
// for (int j=1; j<=n; j++) if (!visit[j])
// ans[i][j]=ans[j][i]=min(ans[i][j],maxflow);
ans[++tot]=maxflow;
int l=L,r=R;
for (int i=L; i<=R; i++)
if (visit[id[i]])
tmp[l++]=id[i];
else tmp[r--]=id[i];
for (int i=L; i<=R; i++) id[i]=tmp[i];
work(L,l-1); work(r+1,R);
}
int main()
{
// freopen("mincuto.in","r",stdin);
// freopen("mincuto.out","w",stdout);
init();
n=read(),m=read();
for (int i=1; i<=n; i++) id[i]=i;
for (int u,v,w,i=1; i<=m; i++)
u=read(),v=read(),w=read(),insert(u,v,w);
work(1,n);
sort(ans+1,ans+tot+1);
int an=1;
for (int i=2; i<=tot; i++) if (ans[i]!=ans[i-1]) an++;
printf("%d\n",an);
return 0;
}
Day1T1
CQOI2016 Day1 T2:K远点对
涉及算法:凸包/KD-Tree/可并堆
思路:
先把所有点都放到KD Tree里,维护一个小根堆，枚举每个点。每次在kd树种查询的时候，就相当于当前的最优解是堆顶，像查最远点对一样在kd树里查就行了。
CODE:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
long long read()
{
long long x=0,f=1; char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define maxn 100010
#define inf 100000000000000000LL
int n,k,D;
long long sqr(long long a) {return (long long)(a*a);}
struct PointNode
{
int l,r; long long d[2],maxx[2],minn[2];
bool operator <(const PointNode & A) const {return d[D]<A.d[D];}
PointNode (long long x=0,long long y=0) {l=r=0; d[0]=x; d[1]=y;}
}p[maxn];
priority_queue<long long, vector<long long>, greater<long long> > heap;
long long dis(PointNode A,PointNode B) {return sqr(A.d[1]-B.d[1])+sqr(A.d[0]-B.d[0]);}
struct KDTreeNode
{
int rt;
PointNode Point,tree[maxn<<1];
void Update(int now)
{
for (int i=0; i<=1; i++)
{
tree[now].minn[i]=tree[now].maxx[i]=tree[now].d[i];
if (tree[now].l)
tree[now].minn[i]=min(tree[tree[now].l].minn[i],tree[now].minn[i]),tree[now].maxx[i]=max(tree[tree[now].l].maxx[i],tree[now].maxx[i]);
if (tree[now].r)
tree[now].minn[i]=min(tree[tree[now].r].minn[i],tree[now].minn[i]),tree[now].maxx[i]=max(tree[tree[now].r].maxx[i],tree[now].maxx[i]);
}
}
int BuildTree(int l,int r,int dd)
{
int mid=(l+r)>>1;
D=dd; nth_element(p+l,p+mid,p+r+1);
tree[mid]=p[mid];
for (int i=0; i<=1; i++) tree[mid].minn[i]=tree[mid].maxx[i]=tree[mid].d[i];
if (l1,dd^1);
if (r>mid) tree[mid].r=BuildTree(mid+1,r,dd^1);
Update(mid);
return mid;
}
long long dist(int pl,PointNode P)
{
long long re=0;
for (int i=0; i<=1; i++)
re+=max(sqr(P.d[i]-tree[pl].minn[i]),sqr(P.d[i]-tree[pl].maxx[i]));
return re;
}
void Query(int now)
{
long long dl,dr,d0;
d0=dis(tree[now],Point);
if (d0>heap.top()) heap.pop(),heap.push(d0);
if (tree[now].l) dl=dist(tree[now].l,Point); else dl=-inf;
if (tree[now].r) dr=dist(tree[now].r,Point); else dr=-inf;
if (dl>dr)
{
if (dl>heap.top()) Query(tree[now].l);
if (dr>heap.top()) Query(tree[now].r);
}
else
{
if (dr>heap.top()) Query(tree[now].r);
if (dl>heap.top()) Query(tree[now].l);
}
}
}KDTree;
int main()
{
// freopen("farthest.in","r",stdin);
// freopen("farthest.out","w",stdout);
n=read(); k=read();
for (int x,y,i=1; i<=n; i++) x=read(),y=read(),p[i]=PointNode(x,y);
KDTree.rt=KDTree.BuildTree(1,n,0);
for (int i=1; i<=k+k; i++) heap.push(0LL);
for (int i=1; i<=n; i++)
KDTree.Point=p[i],KDTree.Query(KDTree.rt);
printf("%lld\n",heap.top());
return 0;
}
Day1T2
CQOI2016 Day1 T3:手机号码
涉及算法:数位DP/记忆化搜索
思路:
涉及F[i][j][0/1][0/1][0/1][0/1][0/1]表示位数为i，最高位为j,最高位连续两个是否是相同的，是否有连续3个相同的，是否有4，是否有8，前缀和原数前缀的大小关系
枚举k1,k2,k3,k4,k5转移统计答案即可,注意一些细节(记忆化搜索应该比较好实现)
CODE:
#include
#include
#include
#include
using namespace std;
long long F[20][15][2][2][2][2][2],l,r;
int p[20],num;
long long cal(long long x)
{
memset(F,0,sizeof(F));
long long ans=0; int len=0,digit[12],a,b,c,d,e;
while(x){digit[++len]=x%10; x/=10;}
reverse(digit+1,digit+len+1);
F[0][10][0][0][0][0][1]=1;
for (int i=0; i<=len-1; i++)
for (int j=0; j<=10; j++)
for (int k1=0; k1<=1; k1++)
for (int k2=0; k2<=1; k2++)
for (int k3=0; k3<=1; k3++)
for (int k4=0; k4<=1; k4++)
for (int k5=0; k5<=1; k5++)
if (F[i][j][k1][k2][k3][k4])
for (int k=0; k<=9; k++)
{
if (k5 && (k>digit[i+1])) continue;
if (k==j) a=1; else a=0;
if (k2==0) b=(k1+a)==2; else b=k2;
if (k3==0) c=(k==4); else c=k3;
if (k4==0) d=(k==8); else d=k4;
if ((c+d)==2) continue;
if (k5 && (k==digit[i+1])) e=1; else e=0;
F[i+1][k][a][b][c][d][e]+=F[i][j][k1][k2][k3][k4][k5];
}
for (int i=0; i<=9; i++)
for (int k1=0; k1<=1; k1++)
for (int k3=0; k3<=1; k3++)
for (int k4=0; (k4<=1)&&(k4+k3<2); k4++)
ans+=F[len][i][k1][1][k3][k4][0];
return ans;
}
int main()
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",cal(r+1)-cal(l));
return 0;
}
Day1T3
CQOI2016 Day2 T1:密钥破解
涉及算法:数论/Pollard_Rho分解/ExGcd/乘法逆元/快速幂/快速乘/模拟
思路:
用Pollard_Rho分解N,得到P,Q,同时计算出r;剩下的根据题意模拟
利用ExGcd求解e在r意义下的逆元,最后答案用快速幂算出即可
CODE:
#include
#include
#include
#include
#include
#include
using namespace std;
long long read()
{
long long x=0,f=1; char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
long long e,N,c,r,P,Q;
long long Quick_Mul(long long x,long long y,long long p)
{
long long re=0;
for (long long i=y; i; i>>=1,x=(x+x)%p)
if (i&1) re=(re+x)%p;
return re;
}
long long Quick_Pow(long long x,long long y,long long p)
{
long long re=1;
for (long long i=y; i; i>>=1,x=Quick_Mul(x,x,p))
if (i&1) re=Quick_Mul(re,x,p);
return re;
}
void Exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0) {x=1; y=0; return;}
Exgcd(b,a%b,y,x); y-=(a/b)*x;
}
long long GetInv(long long n,long long p)
{
long long x,y;
Exgcd(n,p,x,y);
return (x%p+p)%p;
}
long long Gcd(long long a,long long b)
{
if (b==0) return a;
return Gcd(b,a%b);
}
#define T 10007
long long Pollard_Rho(long long n)
{
long long x,y,cnt=1,k=2;
x=rand()%(n-1)+1; y=x;
while (1)
{
cnt++;
x=(Quick_Mul(x,x,n)+T)%n;
long long gcd=Gcd(abs(x-y),n);
if (1return gcd;
if (x==y) return n;
if (cnt==k) y=x,k<<=1;
}
}
int main()
{
srand(T);
e=read(),N=read(),c=read();
P=Pollard_Rho(N); Q=N/P;
r=(P-1)*(Q-1);
long long Inv=GetInv(e,r);
printf("%lld %lld",Inv,Quick_Pow(c,Inv,N));
return 0;
}
Day2T1
CQOI2016 Day2 T2:路由表
涉及算法:Trie树/单调栈/进制转化
思路:
A/Q操作都对IP进行二进制转化后进行处理
A操作将转化后的IP前掩码为加到Trie树中,结尾打上时间戳标记
Q操作,二进制在Trie树上跑跑,将答案记录下来,排序后统计一下答案即可,或者利用单调栈维护即可
CODE:
#include
#include
#include
#include
#include
using namespace std;
int m,Ip[50];
#define maxn 1000100
int ch[maxn][2],pos[maxn],rt=1,cnt=1,sz=1,ti=0;
void Insert(int *ip,int l,int x)
{
int now=rt;
for (int i=1; i<=l; i++)
{
if (!ch[now][ip[i]])
ch[now][ip[i]]=++sz;
now=ch[now][ip[i]];
}
pos[now]=x;
}
struct Node
{
int a,b;
bool operator <(const Node & A) const
{return a<A.a;}
};
Node stack[maxn]; int top;
int Query(int *ip,int L,int R)
{
int now=rt,re=0,m=-1; top=0;
for (int i=1; i<=32; i++)
{
if (!ch[now][ip[i]]) break;
now=ch[now][ip[i]];
if (pos[now] && pos[now]<=R)
stack[++top]=Node{pos[now],i+1};
}
sort(stack+1,stack+top+1);
for (int i=1; i<=top; i++)
{
Node now=stack[i];
if (mif (now.a>=L) re++;}
}
return re;
}
int main()
{
scanf("%d",&m);
for (int i=1; i<=m; i++)
{
char opt[5]; scanf("%s",opt);
if (opt[0]=='A')
{
ti++; int ip,len=0,l;
memset(Ip,0,sizeof(Ip));
for (int j=1; j<=3; j++)
{
scanf("%d.",&ip);
for (int k=7; k>=0; k--)
Ip[++len]=(1&(ip>>k));
}
scanf("%d/",&ip);
for (int k=7; k>=0; k--) Ip[++len]=(1&(ip>>k));
scanf("%d",&l);
//for (int j=1; j<=len; j++) printf("%d",Ip[j]); puts("");
Insert(Ip,l,ti);
}
if (opt[0]=='Q')
{
int ip,len=0,l,r;
memset(Ip,0,sizeof(Ip));
for (int j=1; j<=3; j++)
{
scanf("%d.",&ip);
for (int k=7; k>=0; k--)
Ip[++len]=(1&(ip>>k));
}
scanf("%d",&ip);
for (int k=7; k>=0; k--) Ip[++len]=(1&(ip>>k));
scanf("%d %d",&l,&r);
//for (int j=1; j<=len; j++) printf("%d",Ip[j]); puts("");
printf("%d\n",Query(Ip,l,r));
}
}
return 0;
}
Day2T2
CQOI2016 Day2 T3:伪光滑数
涉及算法:可持久化可并堆/DP/堆/贪心/暴力
思路:
预处理出$<128"><128$的全部质数,那么很显然,可以对数进行拆分了.
考虑题目中所说的, 所以不妨枚举倍数,对于$prime[i]j">prime[i]^{j}$,扔进堆中
然后从队首取K次即可,对于每次取出的数,除以它的最大质因子,乘上比他最大质因子小的最大的质数,再扔回堆中
可持久化可并堆+DP的方法并不会....(留坑以后来看看)
CODE:
#include
#include
#include
#include
using namespace std;
struct Node
{
long long data; int zs,nt,mp;
bool operator <(const Node & A) const
{return data<A.data;}
}now,tmp;
priority_queue q;
long long n,x; int k,j;
int prime[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127},cnt=31;
int main()
{
scanf("%lld%d",&n,&k);
for (int i=1; i<=cnt; i++)
for (x=j=1; ; j++)
{
x*=(long long)prime[i]; if (x>n) break;
tmp.data=x,tmp.zs=j,tmp.nt=i-1,tmp.mp=i;
//printf("%lld %d %d %d\n",tmp.data,tmp.zs,tmp.nt,tmp.mp);
q.push(tmp);
}
while (k--)
{
now=q.top(); q.pop();
if (now.zs>1)
for (int i=now.nt; i; i--)
{
tmp.data=(long long)now.data/prime[now.mp]*prime[i]; tmp.zs=now.zs-1; tmp.nt=i; tmp.mp=now.mp;
//printf("%lld %d %d %d\n",tmp.data,tmp.zs,tmp.nt,tmp.mp);
q.push(tmp);
}
}
printf("%lld\n",now.data);
return 0;
}
Day2T3
据azui神犇所说..CQOI都是 偏题,语文题,模板题 ...但是感觉今年的题目还是不错的,比较有价值
暴露的一些问题:
1.有题目可以想到正确做法,但是实现起来有差错,细节上的问题尤其容易出现
2.一些实用的算法和数据结构并不熟练,需要重视起来
3.调试的时间过长,发现问题不敏锐,严重影响进度,以后应该加强
启发:
1.对于想不出来最优解的问题,可以考虑想时间复杂度次优的方法,尽可能的优,在实际中能得到大把的分数,或者卡时A
2.数位DP方面需要总结一下技巧和方法,只有总结出了方法,才能面对各种题都不慌
3.认真读题,想题做题时要确保理解了题意,才能更深入的想出优秀的算法,很多时候应该按照题意去模拟
4.一些非反演的数论题,可能只是需要进行一些转化,然后多种东西嵌套求解,不用慌张;对于跟质因子相关的题目,入手点在质因子上,往往能得到高效的结果
UPD:2016.05.24Day1T2(填坑完毕),附上全家福:
京公网安备 11010802041100号