本文共 13196 字，大约阅读时间需要 43 分钟。
【题意】
一个n*m的地图(1≤n, m≤50)，有一个入口和一个出口。给定一个命令序列（上，下，左，右），如果碰到障碍或者边际就忽略。问至少加入或删除多少个的命令，使得能从入口走到出口。
【题解】
f[i][j][k]表示在位置(i,j)，匹配到命令序列的第k项，至少加入或删除多少个的命令。
一场ACM有n题，做第i题要$t_i$的时间。
有n!种读题顺序，做题策略是这样的：
1.先随机读k道题；
2.在读过的题中做用时最少的题（有多个就随便选一个）
3.从没读过的题中随机选一题（如果有的话）
4.如果还有题没有做，跳到步骤2
求n!种情况的罚时之和。
这道题可以做到O(n)（不算排序）
容易知道第i个做出来的题系数为n-i+1
容易知道最后做出来的k-1道题一定是用时前k-1大的。
我们从后往前考虑。
先把时间从大到小排序。
改一下规则，如果在读过的题中有多个用时最少，选下标最大的。
记f[i]表示只考虑前i道题时的答案。
f[1]=t[1]
当1<i<=k时，
$f[i]=f[i-1]*i+i!*t[i]*i$
当k<i<=n时，
这道题如果一旦被读过，就一定会立刻做。
我们要算这道题的贡献和它造成其他题罚时的增量。
分两种情况考虑，
1）这道题是第1道做出来的题
2）这道题是第2...i-k+1道做出来的题目
看程序注释
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 25 using namespace std; 26 27 typedef long long LL; 28 typedef double DB; 29 typedef pair PII; 30 typedef pair PDD; 31 typedef complex CP; 32 typedef vector VI; 33 34 #define mmst(a,v) memset(a,v,sizeof(a)) 35 #define mmcy(a,b) memcpy(a,b,sizeof(a)) 36 #define fill(a,l,r,v) fill(a+l,a+r+1,v) 37 #define re(i,a,b) for(i=(a);i<=(b);i++) 38 #define red(i,a,b) for(i=(a);i>=(b);i--) 39 #define fi first 40 #define se second 41 #define mp(a,b) make_pair(a,b) 42 #define pb(a) push_back(a) 43 #define two(k) (1<<(k)) 44 #define SZ(x) (int(x.size())) 45 #define all(x) (x).begin(),(x).end() 46 #define ire(i,v,x) for(i=0,v=i >1) 50 51 template inline T sqr(T x){ return x*x;} 52 template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;} 53 template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;} 56 const DB Pi=acos(-1.0); 57 58 int gint() 59 { 60 int res=0;bool neg=0;char z; 61 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 62 if(z==EOF)return 0; 63 if(z=='-'){neg=1;z=getchar();} 64 for(;z!=EOF && isdigit(z);res=(res<<3)+(res<<1)+z-'0',z=getchar()); 65 return (neg)?-res:res; 66 } 67 LL gll() 68 { 69 LL res=0;bool neg=0;char z; 70 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 71 if(z==EOF)return 0; 72 if(z=='-'){neg=1;z=getchar();} 73 for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); 74 return (neg)?-res:res; 75 } 76 77 const int maxn=310; 78 const int MOD=1000000007; 79 80 int n,k; 81 LL t[maxn],s[maxn],fact[maxn],f[maxn]; 82 83 bool cmp(LL a,LL b){ return a>b;} 84 85 int main() 86 { 87 freopen("D.in","r",stdin); 88 int i; 89 n=gint();k=gint(); 90 re(i,1,n)t[i]=gint(); 91 sort(t+1,t+n+1,cmp); 92 re(i,1,n)s[i]=(s[i-1]+t[i])%MOD; 93 fact[0]=1;re(i,1,n)fact[i]=fact[i-1]*i%MOD; 94 LL temp=0; 95 re(i,1,k-1)(temp+=t[i]*i)%=MOD; 96 f[1]=t[1]; 97 re(i,2,k)f[i]=(f[i-1]*i%MOD+fact[i]*t[i]%MOD*i%MOD)%MOD; 98 re(i,k+1,n) 99 {100 f[i]=f[i-1]*i%MOD;101 (f[i]+=fact[i-1]*k%MOD*t[i]%MOD*i%MOD)%=MOD;//这道题是第1道做出来的题102 //这道题是第2...i-k+1道做出来的题目103 (f[i]+=fact[i-1]*(i-1+k)*(i-k)/2%MOD*t[i]%MOD)%=MOD;//这道题的贡献104 (f[i]+=f[i-1]-(temp+(s[i-1]-s[k-1])*(k-1))*fact[i-1]%MOD)%=MOD;//它造成其他题罚时的增量105 }106 cout<<(f[n]%MOD+MOD)%MOD<
给定n个点，问用前k个点与剩下的n-k个点建一个凸包，最大面积是多少。
建大小两个凸包。大凸包用n个点建，小凸包用前k个点建。
然后在大凸包上跑就行了。
输出时不能强行转成double。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 25 using namespace std; 26 27 typedef long long LL; 28 typedef double DB; 29 typedef pair PII; 30 typedef pair PDD; 31 typedef complex CP; 32 typedef vector VI; 33 34 #define mmst(a,v) memset(a,v,sizeof(a)) 35 #define mmcy(a,b) memcpy(a,b,sizeof(a)) 36 #define fill(a,l,r,v) fill(a+l,a+r+1,v) 37 #define re(i,a,b) for(i=(a);i<=(b);i++) 38 #define red(i,a,b) for(i=(a);i>=(b);i--) 39 #define fi first 40 #define se second 41 #define mp(a,b) make_pair(a,b) 42 #define pb(a) push_back(a) 43 #define two(k) (1<<(k)) 44 #define SZ(x) (int(x.size())) 45 #define all(x) (x).begin(),(x).end() 46 #define ire(i,v,x) for(i=0,v=i >1) 50 51 template inline T sqr(T x){ return x*x;} 52 template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;} 53 template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;} 56 const DB Pi=acos(-1.0); 57 58 int gint() 59 { 60 int res=0;bool neg=0;char z; 61 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 62 if(z==EOF)return 0; 63 if(z=='-'){neg=1;z=getchar();} 64 for(;z!=EOF && isdigit(z);res=(res<<3)+(res<<1)+z-'0',z=getchar()); 65 return (neg)?-res:res; 66 } 67 LL gll() 68 { 69 LL res=0;bool neg=0;char z; 70 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 71 if(z==EOF)return 0; 72 if(z=='-'){neg=1;z=getchar();} 73 for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); 74 return (neg)?-res:res; 75 } 76 77 const int maxn=110000; 78 79 int n,k; 80 struct Tp 81 { 82 LL x,y; 83 friend LL operator *(Tp p1,Tp p2){ return p1.x*p2.y-p2.x*p1.y;} 84 }p[maxn]; 85 86 bool cmp(Tp a,Tp b){ return a.x!=b.x?a.x 1 && det(sta[top-1],sta[top],p[i])<=0)top--; 98 sta[++top]=p[i]; 99 }100 int d=top;101 red(i,n,1)102 {103 while(top>d && det(sta[top-1],sta[top],p[i])<=0)top--;104 sta[++top]=p[i];105 }106 top--;107 }108 109 Tp q[maxn];int m;110 #define L(x) (x==1?m:x-1)111 #define R(x) (x==m?1:x+1)112 LL solve()113 {114 int i;115 LL S=0;116 q[m+1]=q[1];117 re(i,1,m)S+=q[i]*q[i+1];118 LL res=S,tmp=0;119 int l=1,r=1;120 while(det(sta[1],q[l],q[L(l)])>=0)tmp+=det(q[L(l)],q[l],q[r]),l=L(l);121 re(i,1,top)122 {123 while(det(q[r],q[R(r)],sta[i])<=0)tmp+=det(q[l],q[r],q[R(r)]),r=R(r);124 while(det(q[l],q[R(l)],sta[i])>0)tmp-=det(q[l],q[R(l)],q[r]),l=R(l);125 upmax(res,S-tmp+det(sta[i],q[r],q[l]));126 }127 return res;128 }129 130 int main()131 {132 freopen("E.in","r",stdin);133 freopen("E.out","w",stdout);134 int i;135 n=gint();k=gint();136 re(i,1,n)p[i].x=gint(),p[i].y=gint();137 graham(p,k);138 m=top;139 re(i,1,m)q[i]=sta[i];140 graham(p,n);141 LL ans=solve();142 cout<<(ans>>1);143 if(ans&1)puts(".5");else puts(".0");144 return 0;145 }
一个n*n的棋盘上，有l盏灯。每盏灯可以选择在横向或者纵向的方向照，延伸范围为r。
如果一个空格在横向上被超过1盏灯照，或者在纵向上被超过1盏灯照，那么鬼就会被吓跑。
问是否存在一种方案使得鬼不会被吓跑。
2-SAT。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 25 using namespace std; 26 27 typedef long long LL; 28 typedef double DB; 29 typedef pair PII; 30 typedef pair PDD; 31 typedef complex CP; 32 typedef vector VI; 33 34 #define mmst(a,v) memset(a,v,sizeof(a)) 35 #define mmcy(a,b) memcpy(a,b,sizeof(a)) 36 #define fill(a,l,r,v) fill(a+l,a+r+1,v) 37 #define re(i,a,b) for(i=(a);i<=(b);i++) 38 #define red(i,a,b) for(i=(a);i>=(b);i--) 39 #define fi first 40 #define se second 41 #define mp(a,b) make_pair(a,b) 42 #define pb(a) push_back(a) 43 #define two(k) (1<<(k)) 44 #define SZ(x) (int(x.size())) 45 #define all(x) (x).begin(),(x).end() 46 #define ire(i,v,x) for(i=0,v=i >1) 50 51 template inline T sqr(T x){ return x*x;} 52 template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;} 53 template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;} 56 const DB Pi=acos(-1.0); 57 58 int gint() 59 { 60 int res=0;bool neg=0;char z; 61 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 62 if(z==EOF)return 0; 63 if(z=='-'){neg=1;z=getchar();} 64 for(;z!=EOF && isdigit(z);res=(res<<3)+(res<<1)+z-'0',z=getchar()); 65 return (neg)?-res:res; 66 } 67 LL gll() 68 { 69 LL res=0;bool neg=0;char z; 70 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 71 if(z==EOF)return 0; 72 if(z=='-'){neg=1;z=getchar();} 73 for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); 74 return (neg)?-res:res; 75 } 76 77 const int maxn=1100; 78 79 int n,r,l; 80 int x[maxn],y[maxn]; 81 82 int now,info[2*maxn]; 83 struct Tedge{ int v,next;}edge[2*maxn*maxn]; 84 85 void add(int u,int v) 86 { 87 edge[++now]=(Tedge){v,info[u]};info[u]=now; 88 u^=1;v^=1; 89 edge[++now]=(Tedge){u,info[v]};info[v]=now; 90 } 91 92 int cnt,dfn[2*maxn],low[2*maxn]; 93 int top,sta[2*maxn],vis[2*maxn]; 94 int tot,id[2*maxn]; 95 void dfs(int u) 96 { 97 dfn[u]=low[u]=++cnt; 98 vis[sta[++top]=u]=1; 99 int i,v;100 for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)101 if(!dfn[v])102 dfs(v),upmin(low[u],low[v]);103 else104 if(vis[v])upmin(low[u],dfn[v]);105 if(dfn[u]==low[u])106 {107 tot++;108 while(1){vis[sta[top]]=0;id[sta[top--]]=tot;if(sta[top+1]==u)break;}109 }110 }111 112 int main()113 {114 freopen("H.in","r",stdin);115 int i,j;116 n=gint();r=gint();l=gint();117 re(i,1,l)x[i]=gint(),y[i]=gint();118 mmst(info,-1);now=-1;119 re(i,1,l)re(j,1,i-1)120 {121 if(x[i]==x[j] && abs(y[i]-y[j])<=2*r)add(i<<1,j<<1|1);122 if(y[i]==y[j] && abs(x[i]-x[j])<=2*r)add(i<<1|1,j<<1);123 }124 re(i,1,2*l)if(!dfn[i])dfs(i);125 re(i,1,l)if(id[i<<1]==id[i<<1|1]){printf("NO\n");return 0;}126 printf("YES\n");127 return 0;128 }
一块n*m的地图(1≤n, m≤40)，有一些点是陆地“L”，有一些点是海洋“W”，还有一些未确定“C”。求出一种方案，使得把所有“C”变成“L”或者“W”后，陆地连通块的个数最大。
首先，确定两点：
与“L”的“C”一定不会变成陆地“L”；
新生成的陆地面积一定是1*1
由相邻格子之间相互排斥可以奇偶二分图和最大独立集。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 26 using namespace __gnu_cxx; 27 using namespace std; 28 29 typedef long long LL; 30 typedef double DB; 31 typedef pair PII; 32 typedef pair PDD; 33 typedef complex CP; 34 typedef vector VI; 35 36 #define mmst(a,v) memset(a,v,sizeof(a)) 37 #define mmcy(a,b) memcpy(a,b,sizeof(a)) 38 #define fill(a,l,r,v) fill(a+l,a+r+1,v) 39 #define re(i,a,b) for(i=(a);i<=(b);i++) 40 #define red(i,a,b) for(i=(a);i>=(b);i--) 41 #define fi first 42 #define se second 43 #define mp(a,b) make_pair(a,b) 44 #define pb(a) push_back(a) 45 #define two(k) (1<<(k)) 46 #define SZ(x) (int(x.size())) 47 #define all(x) (x).begin(),(x).end() 48 #define ire(i,v,x) for(i=0,v=i >1) 52 53 template inline T sqr(T x){ return x*x;} 54 template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;} 55 template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;} 58 const DB Pi=acos(-1.0); 59 60 //void enlargestack(){int size=256<<10;char *p=(char*)malloc(size)+size;__asm__("movl %0, %%esp\n"::"r"(p));} 61 62 int gint() 63 { 64 int res=0;bool neg=0;char z; 65 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 66 if(z==EOF)return 0; 67 if(z=='-'){neg=1;z=getchar();} 68 for(;z!=EOF && isdigit(z);res=(res<<3)+(res<<1)+z-'0',z=getchar()); 69 return (neg)?-res:res; 70 } 71 LL gll() 72 { 73 LL res=0;bool neg=0;char z; 74 for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); 75 if(z==EOF)return 0; 76 if(z=='-'){neg=1;z=getchar();} 77 for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); 78 return (neg)?-res:res; 79 } 80 81 const int maxn=50; 82 const int dx[]={ 0,0,1,-1}; 83 const int dy[]={ 1,-1,0,0}; 84 85 int n,m; 86 char s[maxn][maxn]; 87 88 89 int vis[maxn][maxn]; 90 void dfs(int x,int y) 91 { 92 vis[x][y]=1; 93 int i; 94 re(i,0,3) 95 { 96 int tx=x+dx[i],ty=y+dy[i]; 97 if(s[tx][ty]=='L' && !vis[tx][ty])dfs(tx,ty); 98 } 99 }100 101 int ok[maxn][maxn];102 int check(int x,int y)103 {104 if(s[x][y]!='C')return 0;105 int i;106 re(i,0,3)107 {108 int tx=x+dx[i],ty=y+dy[i];109 if(s[tx][ty]=='L')return 0;110 }111 return 1;112 }113 114 int a,b,id[maxn][maxn];115 int info[maxn*maxn],now;116 struct Tedge{ int v,next;}edge[maxn*maxn*4];117 int link[maxn*maxn];118 int flag[maxn*maxn];119 120 void add(int u,int v){edge[++now]=(Tedge){v,info[u]};info[u]=now;}121 122 int dfs2(int u)123 {124 int i,v;125 for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)if(!flag[v])126 {127 flag[v]=1;128 if(!link[v] || dfs2(link[v])){link[v]=u;return 1;}129 }130 return 0;131 }132 int main()133 {134 freopen("G.in","r",stdin);135 freopen("G.out","w",stdout);136 int i,j,k;137 n=gint();m=gint();138 re(i,1,n)scanf("%s\n",s[i]+1);139 int ans=0;140 re(i,1,n)re(j,1,m)if(s[i][j]=='L' && !vis[i][j])ans++,dfs(i,j);141 re(i,1,n)re(j,1,m)ok[i][j]=check(i,j);142 re(i,1,n)re(j,1,m)if(ok[i][j])143 if (((i+j)&1)==0)id[i][j]=++a; else id[i][j]=++b;144 mmst(info,-1);now=-1;145 re(i,1,n)re(j,1,m)if(ok[i][j])146 if(((i+j)&1)==0)147 re(k,0,3)148 {149 int tx=i+dx[k],ty=j+dy[k];150 if(ok[tx][ty])add(id[i][j],id[tx][ty]);151 }152 int res=0;153 re(i,1,a)154 {155 re(j,1,b)flag[j]=0;156 res+=dfs2(i);157 }158 ans+=a+b-res;159 cout< <
转载于:https://www.cnblogs.com/maijing/p/7368180.html
