# 2016中国大学生程序设计竞赛(ccpc 杭州)题解报告

2016-11-02 09:25:00      个评论    来源：queuelovestack的专栏

# Problem 1001 ArcSoft's Office Rearrangement

Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

## Problem Description

ArcSoft, Inc. is a leading global professional computer photography and computer vision technology company.

There are N working blocks in ArcSoft company, which form a straight line. The CEO of ArcSoft thinks that every block should have equal number of employees, so he wants to re-arrange the current blocks intoK new blocks by the following two operations:

- merge two neighbor blocks into a new block, and the new block's size is the sum of two old blocks'.

- split one block into two new blocks, and you can assign the size of each block, but the sum should be equal to the old block.

Now the CEO wants to know the minimum operations to re-arrange current blocks intoK block with equal size, please help him.

## Input

First line contains an integer T, which indicates the number of test cases.

Every test case begins with one line which two integers N and K, which is the number of old blocks and new blocks.

The second line contains N numbers a1, a2, ?, aN, indicating the size of current blocks.

Limits

1≤T≤100

1≤N≤10^5

1≤K≤10^5

1≤ai≤10^5

## Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum operations.

If the CEO can't re-arrange K new blocks with equal size, y equals -1.

3
1 3
14
3 1
2 3 4
3 6
1 2 3

Case #1: -1
Case #2: 2
Case #3: 3

## Problem Idea

【题意】

①合并相邻两个分块，合并后块内的总人数等于两分块人数之和

②将一块分割成两个新块，你可以任意分割，只需满足分割后两个新块的总人数等于原分块

【类型】

【分析】

【时间复杂度&&优化】
O(n)

## Source Code

```/*Sherlock and Watson and Adler*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int s[N];
int main()
{
int t,n,i,p=1;
__int64 k,sum,c,ans;
scanf("%d",&t);
while(t--)
{
ans=c=sum=0;
scanf("%d%I64d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&s[i]);
sum+=s[i];
}
printf("Case #%d: ",p++);
if(sum%k)
{
puts("-1");
continue;
}
k=sum/k;
for(i=1;i<=n;i++)
{
c+=s[i];
while(c>k)
ans++,c-=k;
if(c==k)
c=0;
else
ans++;
}
printf("%I64d\n",ans);
}
return 0;
}```

# Problem 1002 Bomb

Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

## Problem Description

There are N bombs needing exploding.

Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode.

If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.

Now you know the attributes of all bombs, please use theminimum cost to explode all bombs.

## Input

First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which indicates the numbers of bombs.

In the following N lines, the ith line contains four intergers xi, yi, ri and ci, indicating the coordinate of ith bomb is (xi,yi), exploding radius is ri and lighting-cost is ci.

Limits

- 1≤T≤20

- 1≤N≤1000

- ?108≤xi,yi,ri≤10^8

- 1≤ci≤10^4

## Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.

1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4

Case #1: 15

【题意】

【类型】

【分析】

INPUT

5
2 0 2 5
2 2 2 6
2 1 2 7
0 0 1 8
0 -1 1 9

OUTPUT

5

【时间复杂度&&优化】
O(n^2)

## Source Code

```/*Sherlock and Watson and Adler*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 1005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
struct bomb
{
int x,y,r;
}bob[N];
struct edge
{
int v,to;
}e[N*N];
int p,k,h[N],dfn[N],low[N],belong[N],ans;
bool instack[N];
stack s;
int c[N],Min[N],in[N];
{
e[p].v=v;
e[p].to=h[u];
h[u]=p++;
}
void Tarjan(int u)//Tarjan算法求有向图的强连通分量,时间复杂度O(n+m)
{
int i,v,Top;
dfn[u]=low[u]=++k;
s.push(u);//入栈
instack[u]=true;//标记在栈中
for(i=h[u];i+1;i=e[i].to)
{//枚举v的每一条边
v=e[i].v;//v所邻接的边
if(!dfn[v])
{//未被访问
Tarjan(v);//继续向下找
low[u]=min(low[u],low[v]);//更新结点v所能到达的最小次数层
}
else if(instack[v])
low[u]=min(dfn[v],low[u]);
}
if(low[u]==dfn[u])
{
ans++;
while(!s.empty())
{
Top=s.top();
s.pop();
belong[Top]=ans;//出栈结点t属于cnt标号的强连通分量
Min[ans]=min(Min[ans],c[Top]);//强连通分量里花费最小的
instack[Top]=false;//标记不在栈中
if(Top==u)
break;
}
}
}
bool judge(int a,int b)
{
return 1ll*(bob[a].x-bob[b].x)*(bob[a].x-bob[b].x)+1ll*(bob[a].y-bob[b].y)*(bob[a].y-bob[b].y)<=1ll*bob[a].r*bob[a].r;
}
int main()
{
scanf("%d",&t);
while(t--)
{
while(!s.empty())
s.pop();
memset(h,-1,sizeof(h));
memset(in,0,sizeof(in));
memset(instack,false,sizeof(instack));
memset(dfn,0,sizeof(dfn));
memset(belong,0,sizeof(belong));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&bob[i].x,&bob[i].y,&bob[i].r,&c[i]);
Min[i]=inf;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
if(judge(i,j))

for(i=1;i<=n;i++)
if(!dfn[i])
Tarjan(i);
for(i=1;i<=n;i++)
for(j=h[i];j+1;j=e[j].to)
if(belong[i]!=belong[e[j].v])
in[belong[e[j].v]]++;
for(i=1;i<=ans;i++)
if(!in[i])
}
return 0;
}```

# Problem 1003 Car

Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

## Problem Description

Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-decrease real number.

Of course, his speeding caught the attention of the traffic police. Police record N positions of Ruins without time mark, the only thing they know is every position is recorded at an integer time point and Ruins started at 0.

Now they want to know the minimum time that Ruins used to pass the last position.

## Input

First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which is the number of the recorded positions.

The second line contains N numbers a1, a2, ?, aN, indicating the recorded positions.

Limits

1≤T≤100

1≤N≤10^5

0

## Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum time.

1
3
6 11 21

Case #1: 4

【题意】

【类型】

【分析】

【时间复杂度&&优化】
O(n)

## Source Code

```/*Sherlock and Watson and Adler*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int s[N];
int main()
{
int t,n,i,j,p=1;
__int64 ans,a,b,c;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
a=s[n]-s[n-1];b=1;
for(i=n;i>=1;i--)
{
c=s[i]-s[i-1];
b=(b*c+a-1)/a;
a=c;
ans+=b;
}
printf("Case #%d: %I64d\n",p++,ans);
}
return 0;
}```

# Problem 1006 Four Operations

Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

## Problem Description

Little Ruins is a studious boy, recently he learned the four operations!

Now he want to use four operations to generate a number, he takes a string which only contains digits '1' - '9', and split it into 5 intervals and add the four operations '+', '-', '*' and '/' in order, then calculate the result(/ used as integer division).

## Input

First line contains an integer T, which indicates the number of test cases.

Every test contains one line with a string only contains digits '1'-'9'.

Limits

1≤T≤10^5

5≤length of string≤20

## Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.

1
12345

Case #1: 1

【题意】

【类型】

【分析】

y=a+b?c×d / e

【时间复杂度&&优化】

## Source Code

```/*Sherlock and Watson and Adler*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 30;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
char s[N],ch[N];
__int64 ans;
int len;
void dfs(int k,int flag)
{
//printf("%d %d\n",k,flag);
if(len-k<4-flag)
return ;
if(k==len)
{
if(flag==4)
{
int c=0;
__int64 w[5];
memset(w,0,sizeof(w));
for(int i=0;i<k+4;i++)>='0'&&ch[i]<='9')
w[c]=w[c]*10+ch[i]-'0';
else
c++;
//printf("%I64d %I64d %I64d %I64d %I64d\n",w[0],w[1],w[2],w[3],w[4]);
ans=max(ans,w[0]+w[1]-w[2]*w[3]/w[4]);
//printf("#%I64d\n",ans);
}
return ;
}
ch[k+flag]=s[k];
if(flag>1&&flag<4&&k+1<len) ans="-1e18;" case="" d:="" else="" int="" len="strlen(s);" p="1;" pre="" return="">```

# Problem 1011 Kingdom of Obsession

Accept: 0 Submit: 0 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

## Problem Description

There is a kindom of obsession, so people in this kingdom do things very strictly.

They name themselves in integer, and there are n people with their id continuous (s+1,s+2,?,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at position which satisfy

x mod y = 0

Is there any way to satisfy everyone's requirement?

## Input

First line contains an integer T, which indicates the number of test cases.

Every test case contains one line with two integers n, s.

Limits

1≤T≤100.

1≤n≤10^9.

0≤s≤10^9.

## Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.

If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

2 5 14 4 11

## Sample Output

Case #1: No Case #2: Yes

## Problem Idea

【题意】

【类型】 匹配，数论 【分析】

【时间复杂度&&优化】 O(n^3)//匈牙利算法邻接矩阵实现

## Source Code

```/*Sherlock and Watson and Adler*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 778;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
bool v[N],g[N][N];//编号为0~n-1
bool dfs(int u)
{
int i;
for(i=0;i=N)
{
puts("No");
continue;
}
for(i=max(s+1,n+1);i<=s+n;i++)
for(j=1;j<=min(s,n);j++)
if(i%j==0)
g[i-max(s+1,n+1)][j-1]=1;
l=r=min(s,n);
if(hungary()==min(s,n))
puts("Yes");
else
puts("No");
}
return 0;
}```