T1:原根(math)
题目链接：
http://172.16.0.132/senior/#contest/show/2532/0
题目：
题解：
一个数m原根的个数是$phi{(phi{(m)})}$，这个了解一下
其实就是先算出m的欧拉函数值，再从1开始枚举，符合上述定义的就直接输出就好了
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int M,phi,m;
int gcd(int a,int b){if (!b) return a;else return gcd(b,a%b);}
int main()
{
//freopen("math.in","r",stdin);
//freopen("math.out","w",stdout);
scanf("%d",&M);
//if (M==1) {puts("1");return 0;}
m=phi=M;
for (int i=2;i*i<=m;i++)
{
if (m%i) continue;
phi=phi*(i-1)/i;
while (m%i==0) m/=i;
}
if (m>1) phi=phi*(m-1)/m;
m=M;
for (int i=1;i<=m;i++)
{
if (gcd(i,m)!=1) continue;
int re=1;bool fg=1;
for (int j=1;j<phi;j++)
{
re=1ll*re*i%m;
if (re==1) {fg=0;break;}
}
if (!fg) continue;
re=1ll*re*i%m;
if (re==1) printf("%d
",i);
}
return 0;
}
T2:道路覆盖(cover)
题目链接：
http://172.16.0.132/senior/#contest/show/2532/1
题目：
ar把一段凹凸不平的路分成了高度不同的N段，并用H[i]表示第i段高度。现在Tar一共有n种泥土可用，它们都能覆盖给定的连续的k个部分。
对于第i种泥土，它的价格为C[i]，可以使得区间[i,min(n,i+k-1)] 的路段的高度增加E[i]。
Tar要设定一种泥土使用计划，使得使用若干泥土后，这条路最低的高度尽量高，并且这个计划必须满足以下两点要求：
（1）每种泥土只能使用一次。
（2）泥土使用成本必须小于等于M。
请求出这个最低的高度最高是多少。
题解:
我们二分这个高度
发现一个位置的高度仅有它本身的高度和从这个点开始向前$k$个位置是否用泥土有关
我们可以预处理出对于一个位置$i$向前$k$个位置放不放泥土的状态对第$i$个位置高度的贡献
怎么判断当前答案是否可行呢？我们状压
$dp[i][S]$表示前$i$位全部满足大于等于当前二分的值，向前k位的状态为$S$的最小代价，显然存在$dp[n][S]<=m$则当前答案可行
考虑如何转移
if (h[i+1]+sum[i+1][j>>1]>=now) chkmin(dp[i+1][j>>1],dp[i][j]);
if (h[i+1]+sum[i+1][(j>>1)|(1<<(k-1))]>=now) chkmin(dp[i+1][j>>1|(1<<(k-1))],dp[i][j]+c[i+1]);
有一点小细节注意一下就好
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> using namespace std; const int N=100+15; const int K=12; int n,m,k,S; int h[N],e[N],c[N],sum[N][1<<K],dp[N][1<<K]; inline int read(){ char ch=getchar();int s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void chkmin(int &a,int b){if (b<a) a=b;} bool check(int now){ memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for (int i=0;i<n;i++) { for (int j=0;j<S;j++) { if (dp[i][j]>m) continue; if (h[i+1]+sum[i+1][j>>1]>=now) chkmin(dp[i+1][j>>1],dp[i][j]); if (h[i+1]+sum[i+1][(j>>1)|(1<<(k-1))]>=now) chkmin(dp[i+1][j>>1|(1<<(k-1))],dp[i][j]+c[i+1]); } } for (int j=0;j<S;j++) { if (dp[n][j]<=m) return 1; } return 0; } int main(){ freopen("cover.in","r",stdin); freopen("cover.out","w",stdout); n=read();m=read();k=read(); for (int i=1;i<=n;i++){ h[i]=read();e[i]=read();c[i]=read(); } S=1<<k; for (int i=1;i<=n;i++) for (int j=0;j<S;j++) for (int p=0;p<k;p++) if (!(j&(1<<p))&&i-(k-p)>=0) sum[i][j^(1<<p)]+=e[i-(k-p)+1]; int l=1,r=1e9;int ans; while (l<=r) { int mid=l+r>>1; if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%d ",ans); return 0; }
T3：迷宫花园(maze)
题目链接：
http://172.16.0.132/senior/#contest/show/2532/2
题目：
给定一个一定存在从起点到终点的路径的四联通迷宫。已知Tar左右方向移动的时间为1，上下移动的时间为未知实数v。求当Tar从起点到终点的最短移动时间为已知实数L时，未知实数v是多少。
题解：
显然随着v的增大最短移动时间不会变短，那么我们就可以二分。二分出v之后跑spfa判断最短路是否大于等于len，若成立则$r=mid$，否则$l=mid$
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<queue> #define tt calc(fx,fy) using namespace std; typedef double db; const int N=115; const db eps=1e-7; const db inf=1e9; int T,n,m,stx,sty,edx,edy; db len; int mp[N][N],vis[N*N]; db dist[N*N]; int calc(int x,int y){return (x-1)*m+y;} bool check(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m&&!mp[x][y];} db spfa(db val){ queue<int> q; for (int i=1;i<=n*m;i++) vis[i]=0,dist[i]=inf; int st=calc(stx,sty); vis[st]=1;q.push(st);dist[st]=0; while (!q.empty()){ int k=q.front();q.pop();vis[k]=0; int x=k/m+1,y=k%m; if (!y) y=m; int fx,fy; fx=x-1;fy=y; if (check(fx,fy)&&dist[tt]>dist[k]+val){ dist[tt]=dist[k]+val; if (!vis[tt]) q.push(tt),vis[tt]=1; } fx=x+1;fy=y; if (check(fx,fy)&&dist[tt]>dist[k]+val){ dist[tt]=dist[k]+val; if (!vis[tt]) q.push(tt),vis[tt]=1; } fx=x;fy=y-1; if (check(fx,fy)&&dist[tt]>dist[k]+1){ dist[tt]=dist[k]+1; if (!vis[tt]) q.push(tt),vis[tt]=1; } fx=x;fy=y+1; if (check(fx,fy)&&dist[tt]>dist[k]+1){ dist[tt]=dist[k]+1; if (!vis[tt]) q.push(tt),vis[tt]=1; } } return dist[calc(edx,edy)]; } int main(){ freopen("maze.in","r",stdin); freopen("maze.out","w",stdout); scanf("%d",&T); while (T--){ scanf("%lf%d%d",&len,&n,&m); for (int i=1;i<=n;i++){ char ch=getchar(); while (!(ch=='S'||ch=='E'||ch=='#'||ch==' ')) ch=getchar(); for (int j=1;j<=m;j++) { if (ch=='#') mp[i][j]=1; else { mp[i][j]=0; if (ch=='S') stx=i,sty=j; if (ch=='E') edx=i,edy=j; } ch=getchar(); } } db l=0,r=10; while (r-l>eps){ db mid=(r+l)/2; if (spfa(mid)>=len) r=mid; else l=mid; } printf("%.5lf ",l); } return 0; }