HDU 2817 A
给你 4 个数 a b c k
前三个可能是等差或者等比数列的前三项 求第K项 % 200907
等比求一下快速幂
#include <iostream> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std ; #define ll __int64 #define MAXN 5000 #define mod 200907 ll Quick(ll a,int b,int c) { ll ans=1; a=a%c; while(b>0) { if(b&1) ans=(ans*a)%c; b>>=1; a=(a*a)%c; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { ll a,b,c,d,q; int k; ll an; scanf("%lld%lld%lld%d",&a,&b,&c,&k); if(b-a==c-b) { d=b-a; an=(a%mod+((d%mod)*(k-1))%mod+mod)%mod; } else { q=b/a; an=((a%mod)*Quick(q,k-1,mod)+mod)%mod; } printf("%lld ",an); } return 0; }
B 并查集 下面的点为根
#include <iostream> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std ; #define ll __int64 #define MAXN 30100 #define mod 200907 int z[MAXN]; //父亲 int w[MAXN];// 下面有多少 int num[MAXN]; //以 i 为根 节点数目-1 int find1(int a) { if(a==z[a]) return a; else { int fa=z[a]; z[a]=find1(fa); w[a]+=w[fa]; return z[a]; } } int main() { int t; scanf("%d",&t); for(int i=1;i<=30000;i++) z[i]=i; while(t--) { char s[10]; int x,y; scanf("%s",s); if(s[0]=='M') { scanf("%d%d",&x,&y); int fx,fy; fx=find1(x); fy=find1(y); if(fx!=fy) { z[fx]=fy; w[fx]+=num[fy]+1;//这个点要加到fy的下一层 num[fy]+=num[fx]+1; //把fx的数目加上 } } else { scanf("%d",&x); int fx=find1(x);//更新一下 printf("%d ",w[x]); } } return 0; }
C 二分匹配
w[i][j] =1 那么 i 行到 j 建边 然后匹配 路径的话 从前往后走就行了
#include <iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<deque> #include<queue> using namespace std ; #define ll __int64 #define MAXN 110 #define inf 1000000007 int z[MAXN][MAXN]; struct node { int u,v,next; }edge[20010]; int cnt; int head[2*MAXN]; int fa[220]; bool vis[220]; void add(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } bool dfs(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]==1) continue; if(fa[v]==-1) { fa[v]=u; return 1; } vis[v]=1; if(dfs(fa[v])) { fa[v]=u; return 1; } } return 0; } int fa1[220]; int main() { int n; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); memset(fa,-1,sizeof(fa)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&z[i][j]); cnt=0;//行 1 - n 新行 n+1 n+n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(z[i][j]==1) { add(i,j+n); add(j+n,i); } } } int ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } if(ans==n) { for(int i=n+1;i<=n*2;i++) fa1[fa[i]]=i-n; int fa2[220];; for(int i=n+1;i<=n*2;i++) fa2[fa[i]]=i-n; ans=0; for(int i=1;i<=n;i++) { if(fa2[i]!=i) { ans++; for(int j=i+1;j<=n;j++) { if(fa2[j]==i) { swap(fa2[j],fa2[i]); break; } } } } printf("%d ",ans); for(int i=1;i<=n;i++) { if(fa1[i]!=i) { for(int j=i+1;j<=n;j++) { if(fa1[j]==i) { printf("R %d %d ",i,j); swap(fa1[j],fa1[i]); break; } } } } } else printf("-1 "); } return 0; }
F 广搜 我还以为是dfs 加最短路 难受 放优先队列里头直接跑 也没有证明
#include <iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<deque> #include<queue> using namespace std ; #define ll __int64 #define MAXN 1010 #define inf 1000000007 struct node { int x,y,step; friend operator < (node a, node b) { return a.step>b.step; } }; priority_queue<node>q1; char z[MAXN][MAXN]; bool vis[MAXN][MAXN]; int s1[4]={1,0,-1,0}; int s2[4]={0,1,0,-1}; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==n) break; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) scanf("%s",z[i]+1); int sx,sy,ex,ey; while(!q1.empty()) q1.pop(); scanf("%d%d%d%d",&sx,&sy,&ex,&ey); vis[sx][sy]=1; node a; a.x=sx; a.y=sy; a.step=0; q1.push(a); while(!q1.empty()) { node now=q1.top(); q1.pop(); if(now.x==ex&&now.y==ey) { printf("%d ",now.step); break; } for(int i=0;i<4;i++) { node b; b.x=now.x+s1[i]; b.y=now.y+s2[i]; if(b.x>=1&&b.x<=n&&b.y>=1&&b.y<=m&&(!vis[b.x][b.y])) { vis[b.x][b.y]=1; if(z[now.x][now.y]=='X') { if(z[b.x][b.y]=='X') b.step=now.step; else b.step=now.step+1; } else { if(z[b.x][b.y]=='.') b.step=now.step+1; else b.step=now.step; } q1.push(b); } } } } return 0; }
H裸的线性欧拉筛nlonglong(n)
处理出来前缀和
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; long long f[3000005]; void get_eular() { for(int i=2;i<3000001;i++) { if(!f[i]) { for(int j=i;j<3000001;j+=i) { if(!f[j]) f[j]=j; f[j]=f[j]/i*(i - 1); } } } for (int i=3;i<3000001;i++) { f[i]+=f[i-1]; } } int main() { get_eular(); int a,b; while(~scanf("%d %d",&a,&b)) { printf("%lld ",f[b]-f[a-1]); } return 0; }