A：
题干：
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi要将一个01串S传输给小Ho，由于S非常长，所以小Hi决定用长度为N的2个数组A = [A1, A2, ..., AN]和B = [B1, B2, ..., BN]表示S。
具体来讲，是指S由N段连续的字符串组成，其中第i段包含Ai个Bi。其中Bi可能是0或1。
例如 A = [1, 2, 3, 4], B = [1, 0, 0, 1]表示S = "1000001111"。
现在小Ho想把S变成一个01交错的字符串。请你帮他计算他最少要改变S中多少个字符才能达成？
输入
第一行包含一个整数N。
第二行包含N个整数，A1, A2, A3, ... AN。
第三行包含N个整数，B1, B2, B3, ... BN。
1 <= N <= 100000
1 <= Ai <= 100000
0 <= Bi <= 1
输出
一个整数代表答案
样例输入
4
1 2 3 4
1 0 0 1 样例输出
4 解题报告：
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX],b[MAX];
int main()
{
int n;
cin>>n;
ll sum = 0;
for(int i = 1; i<=n; i++) scanf("%d",a+i),sum += a[i]/2;
for(int i = 1; i<=n; i++) scanf("%d",b+i);
//开头是1
ll ans1 = 0;
bool sd = 1;
for(int i = 1; i<=n; i++) {
if(b[i] == sd) {
ans1 += a[i]/2;
if(a[i]&1) sd = !sd;
}
else {
ans1 += (a[i]+1)/2;
if(a[i]&1) sd = !sd;
}
}
ll ans2 = 0;
sd = 0;
for(int i = 1; i<=n; i++) {
if(b[i] == sd) {
ans2 += a[i]/2;
if(a[i]&1) sd = !sd;
}
else {
ans2 += (a[i]+1)/2;
if(a[i]&1) sd = !sd;
}
}
printf("%lld\n",min(ans1,ans2));
return 0 ;
}
B：
题干：
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi有NxM的方格矩阵，每个方格的高度是Hij。例如如下是2x3的方格矩阵和每个方格的高度：
--> 1 3 4
左 2 5 3
视 ^
图 |
前视图
左边看过去，可以得到方格矩阵的左视图L = [L1 ... LN]；从前边看过去，可以得到方格矩阵的前视图F = [F1 ... FM]。
例如上例中L = [4, 5], F = [2, 5, 4]。
现在小Ho不知道每个方格的高度，只知道这些方格的左视图和前视图。他发现只知道左视图和前视图并不一定能唯一确定一个方格矩阵。
例如
2 4 4
2 5 4
的左视图和前视图也是L = [4, 5]和F = [2, 5, 4]。
于是小Ho想知道，对于所有可能的方格矩阵，格子高度之和最大是多少。
输入
第一行包含两个整数N和M。
第二行包含N个整数L1, L2, ... LN，代表左视图。
第三行包含M个整数F1, F2, ... FM，代表前视图。
1 <= N, M <= 1000
1 <= Li, Fi <= 1000
输出
一个整数代表答案
样例输入
2 3
4 5
2 5 4 样例输出
21 解题报告：
N*M暴力跑就行了。枚举每一个看他可以达到的最大值。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int n,m;
int h[MAX],q[MAX];
int main()
{
ll ans = 0;
cin>>n>>m;
for(int i = 1; i<=n; i++) cin>>h[i];
for(int i = 1; i<=m; i++) cin>>q[i];
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
ans += min(h[i],q[j]);
}
}
cout <<ans;
return 0 ;
}
C：
题干：
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定N个整数A1, A2, ... AN。现在小Ho可以任意从中取出两个整数X，Y凑成一个数对(X, Y)，只要满足Y = 2X。
如果每个Ai最多被取出一次，请你帮小Ho计算他最多能凑出多少个数对？
输入
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
1 <= N <= 100000
1 <= Ai <= 100000
输出
一个整数代表答案
样例输入
5
1 2 4 8 16 样例输出
2 解题报告：
这题数据范围没有加满，所以可以用数组来计数（AC代码1），这题Ai加到1e18也可以做（AC代码2）。
AC代码1：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;
int n;
int a[100005];
int cnt[100005];
int main() {
scanf("%d",&n);
for(int i=0; i<n; i++)scanf("%d",&a[i]),cnt[a[i]]++;
sort(a,a+n);
for(int i=0; i<n; i++) {
if(a[i]%2==0&&cnt[a[i]/2]) {
ans++;
cnt[a[i]/2]--;
cnt[a[i]]--;
}
}
cout<<ans;
return 0;
}
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
multiset<int> ms;
int a[MAX],n;
int main()
{
int ans = 0;
cin>>n;
for(int i = 1; i<=n; i++) {
cin>>a[i];
ms.insert(a[i]);
}
auto it = ms.begin();
for(int i = 1; i<=n/2; i++) {
while(ms.find((*it)*2) == ms.end() && it != ms.end()) ++it;
if(it != ms.end()) {
auto itt = ms.find((*it)*2);
ans++;
ms.erase(itt);
itt = it;
++it;
ms.erase(itt);
}
else break;
}
cout <<ans;
return 0 ;
}
D：
题干：
时间限制:20000ms
单点时限:2000ms
内存限制:256MB
描述
H市的土地如下图所示，呈现NxM块区域，每一块区域都有自己的高度Hij。
+---+---+---+---+---+---+
|H11|H12|H13|H14|...|H1M|
+---+---+---+---+---+---+
|H21|H22|H23|H24|...|H2M|
+---+---+---+---+---+---+
. . . . . . .
|HN1|HN2|HN3|HN4|...|HNM|
+---+---+---+---+---+---+
为了使以后的城市交通比较便利，H市决定将土地进行平整，使得所有的区域高度相等。已知将1个单位的土地移动到相邻的区域需要花费1的费用，同时当前区域的高度降低1，接收土地的区域高度增加1。那么将所有的区域调整到相同的高度所需的最小费用是多少呢？
输入
第一行包含两个整数N和M。
以下N行包含一个NxM的矩阵H。
0 <= Hij <= 1000
1 <= N, M <= 50
输出
一个整数代表答案
样例输入
2 2
3 4
6 7 样例输出
4 解题报告：
一眼网络流。先计算出最终平衡时所有点的高度值sum（可以计算出，相当于已知）。建图：建一个起点连向所有可以高度减少的点，流量是h[i][j]-sum（因为他必须减少），费用是0；新建一个汇点，高度需要增加的点连向汇点，流量是sum-h[i][j]，费用是0，那么这样建图首先保证了源点流出的流量==汇点流入的流量，这也就保证了流量不会丢失，也就是最大流就是这么大，所以满足了我们需要求最小费用，的要求。相当于是我通过建图，首先固定了最大流（因为新建的源点到新建的汇点，最大流肯定就是min（源点连出的所有的边的流量之和，汇点流入的所有的边的流量之和），而这两者相同，所以最大流已经确定了，就是源点连出的所有边的流量之和，也就是源点流出的流量），然后跑模板去求最小费用就行了。
不过这题他数据错了你敢信，，，给的范围根本不是50*50的，，而且远大于这个，，怪不得一直RE。。。
另一种建图方式：起点到每一个点都有一个流量h[i][j]费用0的边，每个点都到终点有一个流量sum费用0的边，然后每个点向四周连边。合法性的证明参考上一种建图方式。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN = 70000;
const int MAXM = 100005;
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,m;
int N;//节点总个数，节点编号从 0 ～ N-1
void init(int n) {
N = n;
tol = 0;
memset(head, -1,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 = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t) {
queue<int>q;
for(int i = 0; i <= N; i++) {
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i !=-1; 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] ==-1)return false;
else return true;
}
//返回的是最大流，cost 存的是最小费用
int minCostMaxflow(int s,int t,int &cost) {
int flow = 0;
cost = 0;
while(spfa(s,t)) {
int Min = INF;
for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {
if(Min > edge[i].cap-edge[i].flow)
Min = edge[i].cap-edge[i].flow;
}
for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {
edge[i].flow += Min;
edge[i^1].flow-= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int nx[]={0,1,0,-1};
int ny[]={1,0,-1,0};
int id(int i,int j) {
return (i-1)*m+j;
}
int h[555][555];
int main()
{
while(~scanf("%d%d",&n,&m)) {
init(n*m+22);
int st=0,ed=n*m+1,sum = 0;
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
scanf("%d",&h[i][j]);sum += h[i][j];
}
}
sum /= (n*m);
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
if(h[i][j] > sum) addedge(st,id(i,j),h[i][j] - sum,0);
else if(h[i][j] < sum) addedge(id(i,j),ed, sum - h[i][j],0);
}
}
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
for(int k = 0; k<4; k++) {
int tx = i + nx[k];
int ty = j + ny[k];
if(tx<1||tx>n||ty<1||ty>m) continue;
addedge(id(i,j),id(tx,ty),INF,1);
}
}
}
int cost;
int ans = minCostMaxflow(st,ed,cost);
printf("%d\n",cost);
}
return 0 ;
}
京公网安备 11010502036488号