A
lcm(A,B)显然是循环节 然而仅仅这样不行 还有一点规律
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> #include<queue> using namespace std; #define inf 1000000007 #define MAXN 1100 #define ll long long ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll get(ll p,ll a,ll b) { ll A=p%a; ll B=p%b; if(A>B) return A-B; else return B-A; } ll solve(ll n,ll a,ll b) { ll a1=a,b1=b; ll v,p=0; ll ans=0; while(p<n) { if(a1<b1) { v=a1; a1=a1+a; } else { v=b1; b1=b1+b; } v=min(v,n); ans=ans+get(p,a,b)*(v-p); //printf("%lld %lld %lld %lld %lld %lld ",p,a,b,get(p,a,b),v-p,ans); p=v; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { ll n,a,b; scanf("%lld%lld%lld",&n,&a,&b); ll lcm=a/gcd(a,b)*b; // printf("%lld %lld ",a,b); ll k=n/lcm; ll ans=solve(lcm,a,b)*k+solve(n-lcm*k,a,b); printf("%lld ",ans); } return 0; }
F
dp[ i ][ j ][ k ] 走到i 踩过j个陷阱 k = (0,1) 起点是不是陷阱
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> #include<queue> #include<stack> using namespace std; #define inf 1000000007 #define MAXN 50010 #define ll long long int w[MAXN],is[MAXN]; struct node { int v,next; }edge[MAXN<<1]; int cnt; int head[MAXN]; int dp[MAXN][5][2]; void add(int u,int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } int ans; int n,m; void dfs(int u,int fa) { dp[u][is[u]][is[u]]=w[u]; ans=max(ans,dp[u][is[u]][is[u]]); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; dfs(v,u); for(int j=0;j<=m;j++) { for(int k=0;k+j<=m;k++) { if(j+k<=m) ans=max(ans,dp[u][j][1]+dp[v][k][1]); if(j+k<m) ans=max(ans,dp[u][j][0]+dp[v][k][0]); if(j!=m) ans=max(ans,dp[u][j][0]+dp[v][k][1]); if(k!=m) ans=max(ans,dp[u][j][1]+dp[v][k][0]); } } for(int j=0;j<m;j++) { dp[u][j+is[u]][0]=max(dp[u][j+is[u]][0],dp[v][j][0]+w[u]); dp[u][j+is[u]][1]=max(dp[u][j+is[u]][1],dp[v][j][1]+w[u]); } if (!is[u]) dp[u][m][1]=max(dp[u][m][1],dp[v][m][1]+w[u]); } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d%d",&w[i],&is[i]); memset(head,-1,sizeof(head)); cnt=0; for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } ans=0; for(int i=0;i<n;i++) for(int j=0;j<4;j++) for(int k=0;k<2;k++) dp[i][j][k]=-inf; dfs(0,-1); printf("%d ",ans); } return 0; }
H 暴力
#include"stdio.h" #include"string.h" #define N 301 int n,m; int map[N][N]; int min(int a,int b) { return a<b?a:b; } int fun(int t) { int f; int i,j; int x,y; int a,b; for(i=1;i+t-1<=n;i++) { for(j=1;j+t-1<=m;j++) { f=0; x=i;y=i+t-1; while(x<=y) { a=j;b=j+t-1; while(a<=b) { if(map[x][a]!=map[x][b])break; a++;b--; } if(a<=b)break; x++; } if(x<=y){f=0;continue;} else f=1; a=j;b=j+t-1; while(a<=b) { x=i;y=i+t-1; while(x<=y) { if(map[x][a]!=map[y][a])break; x++;y--; } if(x<=y)break; a++; } if(a<=b){f=0;continue;} else {f=1;break;} } if(f==1)break; } if(f==1)return 1; return 0; } int main() { int T; int i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) scanf("%d",&map[i][j]); } i=min(n,m); for(;i>=1;i--) { if(fun(i)) { printf("%d ",i); break; } } } return 0; }
I
最大独立数
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> #include<queue> using namespace std; #define inf 1000000007 #define MAXN 1100 #define ll long long int head[2020]; struct point { int x,y; }z[MAXN<<1]; struct node { int v,next; }edge[2000010]; int cnt; void add(int u,int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } int fa[2010]; bool vis[2010]; bool dfs(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]) continue; if(fa[v]==-1) { fa[v]=u; return true; } vis[v]=1; if(dfs(fa[v])) { fa[v]=u; return true; } } return false; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==m&&m==0) break; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) scanf("%d%d",&z[i].x,&z[i].y); for(int i=1;i<=m;i++) scanf("%d%d",&z[i+n].x,&z[i+n].y); cnt=0; for(int i=1;i<=n;i++) { for(int j=n+1;j<=n+m;j++) { if(z[i].x==z[j].x&&z[i].y==z[j].y||z[i].x==z[j].x&&z[i].y==z[j].y+1||z[i].x+1==z[j].x&&z[i].y==z[j].y||z[i].x+1==z[j].x&&z[i].y==z[j].y+1) { add(i,j); add(j,i); } } } memset(fa,-1,sizeof(fa)); int ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d ",n+m-ans); } return 0; }