| ID | Title | Hint |
|---|---|---|
| A | Impasse (+) | |
| B | Chess | |
| C | An interesting game | 最小费用最大流 |
| D | n a^o7 ! | |
| E | Fruit Ninja I | dp |
| F | Pixel density | 无 |
| G | Mine Number | dfs |
| H | The Best Seat in ACM Contest | 无 |
| I | Pick apples | 贪心，背包 |
| J | Fruit Ninja II | 积分 |
B.
d.国际象棋？就是求能被0~16个棋子吃掉的棋子分别有几个。
s.当时有点思路，感觉对。但是时间好像不大够，也没敲。
用二分查找，查询周围16个位置有棋子没，能不能把它吃掉。
棋子个数n <= 10^5。
10^5*16*log(10^5)<=4*10^7
C.
d.
s.这个题感觉也可以，不知道为啥wa了。
感觉直接暴力贪心就行啊，题意理解错了吗？
c.上个刁丝测试代码。。。数据比较大的时候可以找到不同的，但是还是不懂为什么贪心不行。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include<string.h>
#include <vector>
#include <queue>
#include<time.h>
using namespace std;
const int maxn=;
const int oo=0x3f3f3f3f;
struct Edge
{
int u, v, cap, flow, cost;
Edge(int u, int v, int cap, int flow, int cost):u(u), v(v), cap(cap), flow(flow), cost(cost) {}
};
struct MCMF
{
int n, m, s, t;
vector<Edge> edge;
vector<int> G[maxn];
int inq[maxn], d[maxn], p[maxn], a[maxn];
void init(int n)
{
this->n=n;
for(int i=; i<n; i++)
G[i].clear();
edge.clear();
}
void AddEdge(int u, int v, int cap, int cost)
{
edge.push_back(Edge(u, v, cap, , cost));
edge.push_back(Edge(v, u, , , -cost));
m=edge.size();
G[u].push_back(m-);
G[v].push_back(m-);
}
bool spfa(int s, int t, int& flow, int& cost)
{
memset(d, 0x3f, sizeof d);
memset(inq, , sizeof inq);
d[s]=, inq[s]=, p[s]=, a[s]=oo; queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=;
for(int i=; i<G[u].size(); i++)
{
Edge& e=edge[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost)
{
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u], e.cap-e.flow);
if(!inq[e.v])
{
q.push(e.v);
inq[e.v]=;
}
}
}
}
if(d[t]==oo)return false;
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s)
{
edge[p[u]].flow+=a[t];
edge[p[u]^].flow-=a[t];
u=edge[p[u]].u;
}
return true;
}
int MinCost(int s, int t)
{
int flow=, cost=;
while(spfa(s, t, flow, cost));
return cost;
}
} net; int a[maxn], b[maxn]; struct node{
int h;
int id;
int h2;
}a2[],a3[]; bool cmp(node a,node b){
if(a.h!=b.h)return a.h<b.h;
return a.h2<b.h2;
}
bool cmp2(node a,node b){
if(a.h!=b.h)return a.h<b.h;
return a.h2<b.h2;
} int test1[]={,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,
};
int test2[]={
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,
}; int temp; int f(int N,int M,int K,int b[]){ int T;
//int N,M,K;
//int a[1005],b[1005];
int i;
int ca=;
int sum;
//int a2[1005],a3[1005];
int p1,p2,p3,p4,q1,q2;
int t1,t2;
bool use[]; //scanf("%d",&T); //while(T--){ //scanf("%d%d%d",&N,&M,&K); //for(i=0;i<N;++i){
// scanf("%d",&a[i]);
//}
sum=;
for(i=;i<N-;++i){
sum=sum+abs(a[i]-a[i+]);
temp=sum; if(a[i]>a[i+]){
a2[i].h=a[i];
a2[i].h2=a[i+]; a3[i].h=a[i+];
a3[i].h2=a[i]; a2[i].id=i;
a3[i].id=i;
}
else{
a2[i].h=a[i+];
a2[i].h2=a[i]; a3[i].h=a[i];
a3[i].h2=a[i+]; a2[i].id=i;
a3[i].id=i;
}
/*
cout<<"i: "<<i<<" a2[i].h "<<a2[i].h<<endl;
cout<<"i: "<<i<<" a2[i].h2 "<<a2[i].h2<<endl;
*/
}
/*
i=1;
cout<<"##"<<endl;
cout<<"i: "<<i<<" a2[i].h "<<a2[i].h<<endl;
cout<<"i: "<<i<<" a2[i].h2 "<<a2[i].h2<<endl;
*/
/*
i=1;
cout<<"##"<<endl;
cout<<"i: "<<i<<" a2[i].h "<<a2[i].h<<endl;
cout<<"i: "<<i<<" a2[i].h2 "<<a2[i].h2<<endl;
*/ sort(a2,a2+(N-),cmp);
sort(a3,a3+(N-),cmp2);
/*
i=1;
cout<<"##"<<endl;
cout<<"i: "<<i<<" a2[i].h "<<a2[i].h<<endl;
cout<<"i: "<<i<<" a2[i].h2 "<<a2[i].h2<<endl;
*/
/*
i=1;
cout<<"##"<<endl;
cout<<"i: "<<i<<" a2[i].h "<<a2[i].h<<endl;
cout<<"i: "<<i<<" a2[i].h2 "<<a2[i].h2<<endl;
*/ //for(i=0;i<M;++i){
// scanf("%d",&b[i]);
//}
sort(b,b+M); p1=;p2=N-;
p3=;p4=N-;
q1=;q2=M-;
memset(use,false,sizeof(use));
for(i=;i<K;++i){ if(p1<||p2<||p3<||p4<||q1<||q2<){
cout<<"越界"<<endl;
}
if(p1>N-||p2>N-||p3>N-||p4>N-||q1>M-||q2>M-){
cout<<"越界2"<<endl;
} while(use[a2[p1].id]==true){
++p1;
}
//cout<<"p1 "<<p1<<endl;
t1=b[q2]-a2[p1].h;
//cout<<"t1 "<<t1<<endl;
if(t1<){
t1=;
}
while(use[a3[p4].id]==true){
--p4;
} //cout<<"p4 :"<<p4<<endl;
t2=a3[p4].h-b[q1];
//cout<<"t2 "<<t2<<endl;
if(t2<){
t2=;
} if(t1>t2){
sum=sum+*t1;
use[a2[p1].id]=true; //
//cout<<a2[p1].id<<"### t1: "<<t1<<endl; ++p1;
--q2; }
else{
sum=sum+*t2;
use[a3[p4].id]=true; //
//cout<<a3[p4].id<<"else t2: "<<t2<<endl; --p4;
++q1;
} //cout<<"i:"<<i<<",sum:"<<sum<<endl;
} //printf("Case %d: %d\n",++ca,sum); return sum; // } } int main()
{ int ccc[maxn];
int tot;
int T, kase=;
//scanf("%d", &T);
T=;
T=;
srand(time(NULL));
while(T--)
{
int n, m, k, ans=; n=;
m=;
k=; n=;
m=;
k=;
//scanf("%d%d%d", &n, &m, &k);
net.init(n+);
memset(b, , sizeof b); for(int i=; i<n; i++){
a[i]=rand()%; //a[i]=test1[i]; //scanf("%d", a+i);
} tot=;
for(int i=; i<m; i++)
{
int x;
/*
x=rand()%31;
//scanf("%d", &x);
b[x]++;
ccc[tot++]=x; */
// /* int fuck=rand()%;
b[fuck]++;
ccc[tot++]=fuck;
// */ }
for(int i=; i<n; i++)
{
ans+=abs(a[i]-a[i-]);
net.AddEdge(, i, , );
for(int j=; j<=; j++)
if(b[j])
{
int dis=abs(a[i]-j)+abs(a[i-]-j)-abs(a[i]-a[i-]);
net.AddEdge(i, n+j, , -dis);
}
}
int S=n+, T=S+;
for(int i=; i<=; i++)
if(b[i])
net.AddEdge(i+n, T, b[i], );
net.AddEdge(S, , k, ); int ans2=net.MinCost(S, T);
int ans1=ans-ans2;
//printf("Case %d: %d\n", ++kase, ); //cout<<"贪心："<<endl;
int tanxin=f(n,m,k,ccc); if(ans1!=tanxin){ cout<<"ans:"<<ans<<endl;
cout<<"ans2:"<<ans2<<endl; cout<<"temp:"<<temp<<endl;
cout<<tanxin-temp<<endl; cout<<"yes"<<endl;
cout<<"a:"<<endl;
for(int i=;i<n;++i){
cout<<a[i]<<',';
}
cout<<endl; cout<<"ccc:"<<endl;
for(int i=;i<m;++i){
cout<<ccc[i]<<',';
}
cout<<endl; cout<<endl; cout<<ans1<<"网络流"<<endl;
cout<<tanxin<<"贪心"<<endl;
//return 0; }
} return ;
}
/*
yes
a:
14,20,20,3,10,28,1,19,3,26,29,17,27,11,5,24,3,20,2,8,8,0,11,0,19,29,10,23,17,3,1
4,28,14,8,6,6,8,5,15,1,23,28,17,9,15,20,13,6,3,11,8,6,23,3,1,21,13,20,17,0,16,14
,4,1,18,27,25,21,29,13,19,11,10,22,2,27,0,19,1,8,7,18,7,5,11,22,23,24,22,3,27,3,
17,21,26,8,17,17,17,19,12,28,14,17,28,19,25,12,10,1,30,6,1,1,29,16,0,6,22,27,25,
25,3,0,0,29,8,29,19,24,9,27,15,1,11,28,28,7,0,24,8,17,16,13,14,29,2,12,23,22,12,
25,13,19,21,11,9,10,9,16,16,13,20,22,10,30,29,27,12,23,16,11,22,24,9,15,4,26,4,1
5,19,16,16,19,27,27,30,11,27,27,4,22,19,24,29,10,28,27,2,30,29,19,3,8,21,4,2,4,2
,23,13,6,20,21,5,10,2,8,3,2,3,17,10,7,25,16,13,12,10,23,30,27,22,24,6,10,0,0,30,
7,0,1,1,18,29,5,19,10,8,30,30,0,15,3,17,2,12,22,1,8,20,14,2,15,10,17,4,26,23,19,
15,25,30,17,23,13,18,24,15,1,15,14,5,13,18,10,28,11,11,30,15,0,2,28,4,27,29,21,3
0,1,29,8,6,1,21,13,8,29,24,13,22,1,3,20,8,7,25,26,21,11,3,3,10,9,24,27,5,5,7,9,1
6,17,18,0,5,9,12,10,29,9,20,24,11,4,3,30,12,30,26,6,17,14,20,15,26,17,27,28,15,2
1,15,27,12,24,25,24,17,3,25,9,0,3,15,12,28,6,0,3,17,27,7,26,10,9,13,24,4,21,21,1
9,20,29,15,15,0,24,22,17,30,2,6,21,12,21,16,24,4,10,25,6,18,26,19,5,7,17,18,7,1,
12,13,15,17,21,14,13,17,9,14,4,6,1,13,12,28,1,0,11,29,22,3,25,3,11,21,12,22,5,18
,7,5,0,12,26,11,17,8,14,0,18,6,7,8,30,23,19,0,26,6,15,23,24,30,29,11,20,2,21,14,
4,20,24,1,15,28,30,14,19,8,22,2,23,3,14,20,30,1,1,1,12,17,12,0,2,1,29,18,17,17,5
,17,21,8,8,23,15,11,2,18,30,12,26,9,13,15,11,30,12,23,21,5,18,12,4,20,8,15,19,19
,16,26,24,8,6,23,11,11,9,4,7,22,27,1,24,1,29,19,12,4,18,25,1,5,4,3,25,25,6,0,3,6
,23,23,15,4,6,21,10,20,25,19,11,4,26,4,28,8,8,22,26,12,6,20,28,24,7,4,11,25,28,2
3,0,25,1,3,0,2,10,11,20,4,21,8,15,11,10,6,1,30,2,6,2,6,0,9,19,13,27,30,21,13,18,
17,10,21,27,23,2,5,13,15,10,4,4,18,10,9,5,7,10,24,19,12,2,12,26,6,25,8,18,3,13,1
9,16,19,15,28,11,16,8,29,15,13,23,24,2,2,19,0,7,23,14,2,28,22,2,0,26,16,18,11,19
,0,10,19,5,26,8,8,8,13,5,30,20,29,21,30,3,7,29,27,19,28,13,2,15,18,28,13,5,24,13
,15,27,9,29,0,7,16,28,12,1,9,4,8,6,12,11,12,14,22,28,20,14,8,17,25,20,13,16,6,8,
3,7,7,28,17,23,17,13,16,0,19,23,5,17,6,20,21,9,14,30,2,26,7,5,30,24,2,10,23,22,8
,19,4,9,27,29,11,4,13,23,8,18,6,6,1,18,5,17,6,18,13,6,30,6,28,9,22,9,11,3,3,4,25
,29,3,10,19,26,14,11,29,9,23,4,0,23,29,14,2,21,29,18,10,10,3,2,4,16,20,23,2,5,0,
11,10,1,19,14,10,4,15,22,25,8,10,12,25,15,30,5,2,30,10,5,30,7,3,23,23,19,18,3,10
,13,2,30,16,30,2,6,22,30,3,4,28,6,2,22,3,3,5,20,14,16,12,14,28,12,
ccc:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10
,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,1
1,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,
12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13
,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,1
4,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,
15,15,15,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16
,16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,1
7,17,17,17,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,
18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19
,19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,2
0,20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,21,21,21,21,21,21,21,21,21,21,
21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22
,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,2
3,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,
24,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25
,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,2
7,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,28,28,
28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29
,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,30,30,30,30,30,30,30,30,30,30,3
0,30,30,30,30,30,30,30,30,30,30,30,30,30, 25090网络流
25086贪心 Process returned 0 (0x0) execution time : 1.981 s
Press any key to continue. */ /*
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("data1.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout) using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8; struct Edge
{
int v,f,w,next;
}; Edge eg[66666];
int head[2333],h[2333],hcnt[2333];
int dis[2333],pre[2333];
bool vis[2333];
int tp,ans,minf; void Add(int u,int v,int w,int f)
{
eg[tp].v = v;
eg[tp].w = w;
eg[tp].f = f;
eg[tp].next = head[u];
head[u] = tp++;
} bool bfs(int st,int en)
{
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
queue <int> q;
q.push(st);
dis[st] = 0;
minf = INF;
int u,v,w,f; while(!q.empty())
{
u = q.front();
q.pop();
vis[u] = 0; for(int i = head[u]; i != -1; i = eg[i].next)
{
v = eg[i].v;
w = eg[i].w;
f = eg[i].f;
if(f && (dis[v] == -1 || dis[v] < dis[u]+w))
{
dis[v] = dis[u]+w;
minf = min(f,minf);
pre[v] = i;
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
} if(pre[en] == -1) return false; ans += dis[en];
for(int i = pre[en]; i != -1; i = pre[eg[i^1].v])
{
eg[i].f -= minf;
eg[i^1].f += minf;
} return true;
} int main()
{ int t,n,m,k,x;
scanf("%d",&t);
for(int z = 1; z <= t; ++z)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
memset(hcnt,0,sizeof(hcnt));
tp = 0;
ans = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d",&h[i]);
if(i) ans += abs(h[i]-h[i-1]);
}
while(m--)
{
scanf("%d",&x);
hcnt[x]++;
} //n为起点 0~n-2表示初始第i个山爬到i+1山路程 n+1~n+30表示高1~30的山数 n+31表示起点前的一个点(限流) n+32表示终点
Add(n+33,n+31,0,k);
Add(n+31,n+33,0,0);
for(int i = 0; i <= 30; ++i)
{
if(!hcnt[i]) continue;
Add(n+31,n+i,0,hcnt[i]);
Add(n+i,n+31,0,0);
for(int j = 0; j < n-1; ++j)
{
Add(n+i,j,abs(h[j]-i)+abs(h[j+1]-i)-abs(h[j]-h[j+1]),hcnt[i]);
Add(j,n+i,-abs(h[j]-i)-abs(h[j+1]-i)+abs(h[j]-h[j+1]),0);
}
}
for(int j = 0; j < n-1; ++j)
{
Add(j,n+32,0,1);
Add(n+32,j,0,0);
}
while(bfs(n+33,n+32));
printf("Case %d: %d\n",z,ans);
} return 0;
} */
s.正宗解法，最小费用流
参考：山东省第三届省赛 C 题 – An interesting game(费用流)
ps：参考的这个代码比较快，600ms。 我的好像得1000多。。。
大意：有n个山坡，排成一排，为了增加难度，现在要从m个山坡中挑选k个，插入到原有的n个山坡中，两个原有的山坡中只能插入一个山坡，原有山坡的两侧不能插入。使插入k个山坡后的难度最大，总的难度是相邻两个山坡差值绝对值的和。
思路：训练赛的时候根本没往图论上想，当时想贪心不太可能，还以为是dp。
如果把原问题看做是原有山坡的排列中，两个相邻山坡中间的间隙和m个山坡做匹配的话，就可以看做是，最大流量为k时，最大费用是多少，费用流可以搞。对于最大费用，可以先把费用取负值，求出最小费用后再取负值，就是最大费用。匹配的费用是插入之后的难度的增加量，最大费用加上原山坡的难度，就是答案。
因为n和m的范围是[2, 1000]，直接建图会TLE，发现插入的m个山坡的范围只有[0, 30]，这么小的数据范围一定能优化答案，把插入山坡的高度看做结点，建图。
设置源点S，超级源点SS，汇点T。
S对所有间隙连边，容量1，费用0.
所有间隙对所有高度连边，容量1，费用是难度增加量的相反数.
所有高度对T连边，容量为此高度的个数，费用0.
SS对S连边，容量k，费用0.
答案就是原图的难度-最小费用。
c.最小费用最大流
/*
SPFA版费用流
最小费用最大流，求最大费用最大流只需要取相反数，结果取相反数即可。
点的总数为N，点的编号0~N-1
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=;
const int MAXM=;
const int INF=0x3f3f3f3f;
struct Edge{
int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n){
N=n;
tol=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].cost=-cost;
edge[tol].flow=;
edge[tol].next=head[v];
head[v]=tol++;
}
bool spfa(int s,int t){
queue<int>q;
for(int i=;i<N;i++){
dis[i]=INF;
vis[i]=false;
pre[i]=-;
}
dis[s]=;
vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if(pre[t]==-)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost){
int flow=;
cost=;
while(spfa(s,t)){
int Min=INF;
for(int i=pre[t];i!=-;i=pre[edge[i^].to]){
if(Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
}
for(int i=pre[t];i!=-;i=pre[edge[i^].to]){
edge[i].flow+=Min;
edge[i^].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return flow;
} int main(){ int T;
int N2,M,K;
int X[],Y[];
int YNum[];
int i,j;
int sp,sp2;//源点，源点2
int sc;//汇点
int sum;
int tmp;
int mi_cost;
int ma_flow;
int ca=; scanf("%d",&T); while(T--){ scanf("%d%d%d",&N2,&M,&K); init(N2+); for(i=;i<N2;++i){
scanf("%d",&X[i]);
}
memset(YNum,,sizeof(YNum));
for(i=;i<M;++i){
scanf("%d",&Y[i]);
++YNum[Y[i]];
} sum=;
for(i=;i<N2-;++i){//初始值
sum=sum+abs(X[i]-X[i+]);
} sp=N2+; for(i=;i<N2-;++i){//加边
addedge(sp,i,,);//源点到空隙
for(j=;j<=;++j){
if(YNum[j]){
tmp=abs(X[i]-j)+abs(X[i+]-j)-abs(X[i]-X[i+]);
addedge(i,N2+j,,-tmp);//空隙到M个山丘
}
}
} sp2=N2+;
sc=N2+;
addedge(sp2,sp,K,);
for(i=;i<=;++i){
if(YNum[i]){
addedge(N2+i,sc,YNum[i],);
}
} ma_flow=minCostMaxflow(sp2,sc,mi_cost); printf("Case %d: %d\n",++ca,sum-mi_cost);
} return ;
}
D.
d.好像是按要求输出串
s.没写这个题
c.张
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define MAX 500
using namespace std;
int main ()
{
char temp1[MAX],temp2[MAX],str[MAX];
strcpy(temp1," n5!wpuea^o7!usimdnaevoli");
strcpy(temp2," usimdnaevolin5!wpuea^o7!");
int Len = strlen(temp1);
int T;
scanf("%d",&T);
getchar();
int coun=;
while(T--)
{
gets(str);
int len=strlen(str);
for(int i=,j=; i<len; i++)
{
for(j=; j<Len; j++)
if(str[i]==temp1[j])
break;
if(j<Len) str[i]=temp2[j];
}
printf("Case %d: ",coun++);
for(int i=len-; i>=; i--)
printf("%c",str[i]);
printf("\n");
}
return ;
}
E.
d.水果忍者，水果从上向下掉落，并且只能水平切。
给你n个水果的出现时间，出现的水平位置，和他是否是好水果，切到好水果+1，切到坏水果-1，连续切到三个以上好水果分数加倍。
两刀之间的间隔大于等于m，求能求得的最大分数。
s.先求出每一秒出手能得到的最大的得分，很简单。
再用DP求最大分数。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 10010 int d[MAXN][];//d[i][j]标志i秒j位置水果
int dp[MAXN];//dp[i]表示前i秒获得的最大分数 int main(){ int T;
int n,m;
int t,s,p;
int i,j;
int ma_t;//最大时间
int ma_p[MAXN];//每秒最大位置
int sum,num,ma;//
int ma_sum[MAXN];//每秒可获得的最大分数
int ca=; scanf("%d",&T); while(T--){
scanf("%d%d",&n,&m); memset(d,-,sizeof(d));
ma_t=;
memset(ma_p,,sizeof(ma_p));
for(i=;i<n;++i){
scanf("%d%d%d",&t,&s,&p);
d[t][p]=s;
if(t>ma_t){
ma_t=t;
}
if(p>ma_p[t]){
ma_p[t]=p;
}
} memset(ma_sum,,sizeof(ma_sum));
for(i=;i<=ma_t;++i){//先求出每秒可获得的最大分数
sum=;
num=;
ma=;
for(j=;j<=ma_p[i];++j){
if(d[i][j]==){
++num;
}
else if(d[i][j]==){
if(num>=){
sum=sum+num*;
}
else{
sum=sum+num;
}
if(sum>ma){
ma=sum;
}
num=;
--sum;
if(sum<){
sum=;
}
}
}
if(num>){
if(num>=){
sum=sum+num*;
}
else{
sum=sum+num;
}
if(sum>ma){
ma=sum;
}
}
ma_sum[i]=ma;
} memset(dp,,sizeof(dp));
for(i=;i<=m;++i){
dp[i]=max(dp[i-],ma_sum[i]);//不出手，和出手
}
for(i=m+;i<=ma_t;++i){
dp[i]=max(dp[i-],dp[i-m-]+ma_sum[i]);
} printf("Case %d: %d\n",++ca,dp[ma_t]);
} return ;
}
F.
d.串中提取数字
s.比较坑的是里面空格只要一个就行了
c.当时臃肿的代码。虽然长，但是思路还可以
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std; char str[]; char str1[];
char str2[]; char num1[];
char num2[];
char num3[]; int main(){ int T;
int i;
int len;
int len1,len2;
int p1,p2;
int p3,p4;
int len_num1,len_num2,len_num3;
int j;
double a,a1,a2,b,b1,b2,c,c1,c2;
int p5;
double Dp;
double ans;
int ca=;
int p6,p7; /*
num1 num2 num3
The new iPad 0009.7 inches 2048*1536 PAD
p3 p1 p2 p4 0009.7 2048*1536
p5
p6,07是考虑了后面的小数点，实际好像后面只能是整数 */ scanf("%d",&T);
getchar(); while(T--){
scanf("%[^\n]",str);
getchar(); len=strlen(str); len1=;
len2=;
len_num1=;
len_num2=;
len_num3=; for(i=;i<len;++i){
if(str[i]=='i'){
if(str[i+]=='n'&&str[i+]=='c'&&str[i+]=='h'&&
str[i+]=='e'&&str[i+]=='s'&&str[i+]==' '){
p1=i;
j=i-;
while(str[j]==' '){
--j;
}
while(str[j]!=' '){
num1[len_num1++]=str[j--];
}
while(str[j]==' '){
--j;
}
p3=j;
}
}
if(str[i]=='*'){
if(i>=&&''<=str[i-]&&str[i-]<=''){
if(''<=str[i+]&&str[i+]<=''){
p2=i;
j=i-;
while(str[j]!=' '){
num2[len_num2++]=str[j--];
} j=i+;
while(str[j]!=' '){
num3[len_num3++]=str[j++];
} while(str[j]==' '){
++j;
}
p4=j;
}
}
} } for(i=;i<=p3;++i){
if(str[i]!=' '){
break;
}
}
str1[len1++]=str[i++];
for(;i<=p3;++i){
if(str[i]==' '&&str1[len1-]==' '){
continue;
}
str1[len1++]=str[i];
}
str1[len1]='\0'; for(i=p4;i<len;++i){
if(str[i]==' '&&str2[len2-]==' '){
continue;
}
if('a'<=str[i]&&str[i]<='z'){
str2[len2++]=str[i];
}
else if('A'<=str[i]&&str[i]<='Z'){
str2[len2++]=str[i]+;
}
else{
str2[len2++]=str[i];
} }
str2[len2]='\0'; for(i=len2-;i>=;--i){
if(str2[i]!=' '){
len2=i+;
break;
}
}
str2[i+]='\0'; p5=-;
for(i=;i<len_num1;++i){
if(num1[i]=='.'){
p5=i;
break;
}
}
a=;
a1=;
a2=;
if(p5==-){
for(i=;i<len_num1;++i){
a1=a1+(num1[i]-'')*pow(,i);
}
}
else{
for(i=;i<p5;++i){
a2=a2/+(num1[i]-'')/10.0;
}
for(i=p5+;i<len_num1;++i){
a1=a1+(num1[i]-'')*pow(,(i-(p5+)));
}
} a=a1+a2; if(a==){
printf("Case %d: The %s of %s's PPI is %.2f.\n",++ca,str2,str1,0.0);
continue;
} p6=-;
for(i=;i<len_num2;++i){
if(num2[i]=='.'){
p6=i;
break;
}
}
if(p6==-){
b=;
for(i=;i<len_num2;++i){
b=b+(num2[i]-'')*pow(,i);
}
}
else{
b=;
b1=;
b2=;
for(i=;i<p6;++i){
b2=b2/+(num2[i]-'')/10.0;
}
for(i=p6+;i<len_num2;++i){
b1=b1+(num2[i]-'')*pow(,(i-(p6+)));
}
b=b1+b2;
} p7=-;
for(i=;i<len_num3;++i){
if(num3[i]=='.'){
p7=i;
break;
}
}
if(p7==-){
c=;
for(i=;i<len_num3;++i){
c=c*+(num3[i]-'');
}
}
else{
c=;
c1=;
c2=;
for(i=;i<p7;++i){
c1=c1*+(num3[i]-'');
}
for(i=p7+;i<len_num3;++i){
c2=c2/+(num3[i]-'')/10.0;
} c=c1+c2; } Dp=sqrt(b*b+c*c);
ans=Dp/a; printf("Case %d: The %s of %s's PPI is %.2f.\n",++ca,str2,str1,ans);
} return ;
}
G.
d.类似于扫雷的游戏，这里不是周围8个位置，而是上下左右加它自己5个位置。给出周围多少个雷的数组，求出雷的分布。
s.dfs。先确定第一行，下面的每个位置只看上面的位置即可。
#include<iostream>
#include<stdio.h>
using namespace std; int d[][];
char g[][]; int n,m;
int dir[][]={{-,},{,},{,-},{,},{,}};
bool stop; void dfs(int r,int c); void f1(int r,int c){
int i;
int a,b;
g[r][c]='*';
for(i=;i<;++i){
a=r+dir[i][];
b=c+dir[i][];
if( <=a&&a<n && <=b&&b<m ){
--d[a][b];
}
}
if(c==m-){
a=r+;
b=;
}
else{
a=r;
b=c+;
}
dfs(a,b);
g[r][c]='\0';
for(i=;i<;++i){
a=r+dir[i][];
b=c+dir[i][];
if( <=a&&a<n && <=b&&b<m ){
++d[a][b];
}
}
}
void f2(int r,int c){
int a,b;
g[r][c]='.'; if(c==m-){
a=r+;
b=;
}
else{
a=r;
b=c+;
}
dfs(a,b);
g[r][c]='\0';
} void dfs(int r,int c){
int i,j; if(r==n){
for(i=;i<m;++i){
if(d[n-][i]!=){
return;
}
}
stop=true;
for(i=;i<n;++i){
for(j=;j<m;++j){
printf("%c",g[i][j]);
}
printf("\n");
}
return;
}
int a,b;
if(r==){ bool flag=true;//可以放雷
for(i=;i<;++i){
a=r+dir[i][];
b=c+dir[i][];
if( <=a&&a<n && <=b&&b<m ){
if(d[a][b]==){
flag=false;
break;
}
}
} if(flag){
f1(r,c);
if(stop){
return;
}
}
f2(r,c);
}
else{ if(d[r-][c]==){
f1(r,c);
if(stop){
return;
}
}
else if(d[r-][c]==){
f2(r,c);
}
}
} int main(){ int T;
int i,j;
int ca=;
char str[]; scanf("%d",&T); while(T--){
scanf("%d%d",&n,&m);
for(i=;i<n;++i){
scanf("%s",str);
for(j=;j<m;++j){
d[i][j]=str[j]-'';
}
} printf("Case %d:\n",++ca);
stop=false;
dfs(,); } return ;
}
H.
d.在一个N*M（N,M<=20）的矩阵中，某个位置的值取决于上下左右和它自己，求出所有位置的值。
s.双重循环，直接求一遍就行了。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; int dir[][]={{-,},{,},{,-},{,}}; int main(){ int T;
int N,M;
int s[][];
int v[][];
int i,j;
int a,b;
int ma,ma_i,ma_j;
int ca=;
int k; scanf("%d",&T); while(T--){
scanf("%d%d",&N,&M); for(i=;i<N;++i){
for(j=;j<M;++j){
scanf("%d",&s[i][j]);
}
} memset(v,,sizeof(v)); for(i=;i<N;++i){
for(j=;j<M;++j){
for(k=;k<;++k){
a=i+dir[k][];
b=j+dir[k][];
if(a<||b<||a>=N||b>=M){
v[i][j]-=;
continue;
}
if(s[a][b]>s[i][j]){
v[i][j]=v[i][j]+(s[a][b]-s[i][j]);
}
else{
v[i][j]=v[i][j]-(s[i][j]-s[a][b]);
}
}
}
} ma=v[][];
ma_i=;
ma_j=;
for(i=;i<N;++i){
for(j=;j<M;++j){
if(v[i][j]>=ma){
ma=v[i][j];
ma_i=i;
ma_j=j;
}
}
} printf("Case %d: %d %d %d\n",++ca,ma,ma_i+,ma_j+);
} return ;
}
I.
d.比较直接的一个完全背包，但是大小有这么大V <= 100,000,000
s.很显然，直接来会爆内存了。
但是这个题物品大小不大1 <= S<= 100。然后很萎缩的5000以上贪心，剩余的用完全背包。。。
为什么过了？
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std; struct node{
long long S;
long long P;
double q;
}a[]; bool cmp(node a,node b){
return a.q>b.q;
} int main(){ int T;
long long V;
long long sum;
long long dp[];
long long tmp;
int i,j;
int ca=; scanf("%d",&T); while(T--){
scanf("%lld%lld",&a[].S,&a[].P);
a[].q=(double)(a[].P)/a[].S;
//cout<<a[0].q<<endl;
scanf("%lld%lld",&a[].S,&a[].P);
a[].q=(double)(a[].P)/a[].S;
//cout<<a[1].q<<endl;
scanf("%lld%lld",&a[].S,&a[].P);
a[].q=(double)(a[].P)/a[].S;
//cout<<a[2].q<<endl;
scanf("%lld",&V); sort(a,a+,cmp); sum=V%a[].S; for(i=;;++i){
if(a[].S*i>=){
break;
}
} sum=sum+a[].S*i; memset(dp,,sizeof(dp)); for(i=;i<;++i){
for(j=a[i].S;j<=sum;++j){
tmp=dp[j-a[i].S]+a[i].P;
if(tmp>dp[j]){
dp[j]=tmp;
}
}
} for(i=sum;;--i){
if(dp[i]>){
break;
}
} printf("Case %d: %lld\n",++ca,((V-sum)/a[].S)*a[].P+dp[i]); } return ;
}
J.
d.好像是积分求椭球体的体积。
c.王
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std; int main()
{
int T;
scanf("%d",&T);
int i;
for(i=; i<=T; i++)
{
int a,b,h;
scanf("%d%d%d",&a,&b,&h);
double V;
V=(4.0/)*M_PI*a*b*b;
if(h>=b)
{
printf("Case %d: %.3lf\n",i,V);
}
else
{
double v=M_PI*a*b*(b-h)-M_PI*(1.0*a/b)*(1.0/)*(b*b*b-h*h*h);
if(V-v-v>)
printf("Case %d: %.3lf\n",i,V-v);
else
printf("Case %d: %.3lf\n",i,v);
}
}
return ;
}