ICPC — International Collegiate Programming Contest Asia Regional Contest, Yokohama, 2018–12–09 题解

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

注意！！此题解存在大量假算法，请各位巨佬明辨！

Problem A Digits Are Not Just Characters

题面

Mr. Manuel Majorana Minore made a number of files with numbers in their names. He wants to have a list of the files, but the file listing command commonly used lists them in an order different from what he prefers, interpreting digit sequences in them as ASCII code sequences, not as numbers. For example, the files file10, file20 and file3 are listed in this order.

Write a program which decides the orders of file names interpreting digit sequences as numeric values.

Each file name consists of uppercase letters (from ‘A’ to ‘Z’), lowercase letters (from ‘a’ to ‘z’), and digits (from ‘0’ to ‘9’).

A file name is looked upon as a sequence of items, each being either a letter or a number. Each single uppercase or lowercase letter forms a letter item. Each consecutive sequence of digits forms a number item.

Two item are ordered as follows.

• Number items come before letter items.
• Two letter items are ordered by their ASCII codes. • Two number items are ordered by their values when interpreted as decimal numbers.

Two file names are compared item by item, starting from the top, and the order of the first different corresponding items decides the order of the file names. If one of them, say A, has more items than the other, B, and all the items of B are the same as the corresponding items of A, B should come before.

For example, three file names in Sample Input 1, file10, file20, and file3 all start with the same sequence of four letter items f, i, l, and e, followed by a number item, 10, 20, and 3, respectively. Comparing numeric values of these number items, they are ordered as file3 < file10 < file20.

Input

The input consists of a single test case of the following format.

n s0 s1 . . . sn

The integer n in the first line gives the number of file names (s1 through sn) to be compared with the file name given in the next line (s0). Here, n satisfies 1 ≤ n ≤ 1000. The following n + 1 lines are file names, s0 through sn, one in each line. They have at least one and no more than nine characters. Each of the characters is either an uppercase letter, a lowercase letter, or a digit.

Sequences of digits in the file names never start with a digit zero (0).

Output

For each of the file names, s1 through sn, output one line with a character indicating whether it should come before s0 or not. The character should be “-” if it is to be listed before s0; otherwise, it should be “+”, including cases where two names are identical.

题意

每一次给出一个字符串，你需要不像ASCII的比较方式，字母与字母比，数字与数字比，比串S0小的输出'-'，否则输出'+'。

思路

主要是读懂题面，每一次逐个比较字母或数字就可以。

细节较多。

代码

#include<bits/stdc++.h>
#define DEBUG cerr << "Call out: " << __func__ << "\t" << "Line: " << __LINE__ << "\t :"
using namespace std;long long base[11];
string sr[11];
bool is_d[11];
int MAXLEN = 0;
int LEN = 0;
long long tmp[11];
string tpr[11];
bool is[11];
void trans(string ss)
{
memset(tmp,0,sizeof(tmp));
memset(is,0,sizeof(is));
for (int i=0; i<11; i++)
tpr[i] = "";
int now = 0;
int len = ss.length();
for (int i=0; i<len; i++)
{
if (isdigit(ss[i]))
is[now] = 1,tmp[now] = tmp[now] * 10 + ss[i] - 48;
else
is[now] = 0, tpr[now] += ss[i];
LEN = now;
if (isdigit(ss[i]) != isdigit(ss[i+1])) now++;
}
}int n;
int main()
{
cin >> n;
string s0;
cin >> s0;
trans(s0);
MAXLEN = LEN;
for (int i=0; i<11; i++)
base[i] = tmp[i], is_d[i] = is[i], sr[i] = tpr[i];
for (int i=1; i<=n; i++)
{
string sp;
cin >> sp;
if (sp == s0)
{
puts("+");
continue;
}
trans(sp);
for (int i=0; i<=10; i++)
if (i > LEN)
{
puts("-");
break;
}
else if (i > MAXLEN)
{
puts("+");
break;
}
else if (is_d[i] == 1 && is[i] == 0)
{
puts("+");
break;
}
else if (is_d[i] == 0 && is[i] == 1)
{
puts("-");
break;
}
else if (is_d[i] == 1)
{
if (base[i] > tmp[i])
{
puts("-");
break;
}
else if (base[i] < tmp[i])
{
puts("+");
break;
}
}
else
{
if (sr[i] > tpr[i])
{
puts("-");
break;
}
else if (sr[i] < tpr[i])
{
puts("+");
break;
}
}
}
}


Problem B Arithmetic Progressions

题面

Time Limit: 5 seconds

An arithmetic progression is a sequence of numbers a1, a2, ..., ak where the difference of consecutive members ai+1−ai is a constant (1 ≤ i ≤ k−1). For example, the sequence 5, 8, 11, 14, 17 is an arithmetic progression of length 5 with the common difference 3.

In this problem, you are requested to find the longest arithmetic progression which can be formed selecting some numbers from a given set of numbers. For example, if the given set of numbers is {0, 1, 3, 5, 6, 9}, you can form arithmetic progressions such as 0, 3, 6, 9 with the common difference 3, or 9, 5, 1 with the common difference −4. In this case, the progressions 0, 3, 6, 9 and 9, 6, 3, 0 are the longest.

Input

The input consists of a single test case of the following format. n v1 v2 ··· vn n is the number of elements of the set, which is an integer satisfying 2 ≤ n ≤ 5000. Each vi (1 ≤ i ≤ n) is an element of the set, which is an integer satisfying 0 ≤ vi ≤ 109. vi’s are all different, i.e., vi != vj if i != j.

Output

Output the length of the longest arithmetic progressions which can be formed selecting some numbers from the given set of numbers.

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n;
int a[N];
int f[N][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++) f[i][j] = 2;
for (int i = n; i >= 1; i --)
{
for (int j = i + 1; j <= n; j ++)
{
int k = lower_bound(a + 1, a + 1 + n, 2 * a[j] - a[i]) - a;
if (k >= 1 && k <= n && a[k] - a[j] == a[j] - a[i])
{
f[i][j] = max(f[i][j], f[j][k] + 1);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) ans = max(ans, f[i][j]);
cout << ans << endl;
return 0;
}


Problem C Emergency Evacuation

Time Limit: 3 seconds

The Japanese government plans to increase the number of inbound tourists to forty million in the year 2020, and sixty million in 2030. Not only increasing touristic appeal but also developing tourism infrastructure further is indispensable to accomplish such numbers.

One possible enhancement on transport is providing cars extremely long and/or wide, carrying many passengers at a time. Too large a car, however, may require too long to evacuate all passengers in an emergency. You are requested to help estimating the time required.

The car is assumed to have the following seat arrangement.

• A center aisle goes straight through the car, directly connecting to the emergency exit door at the rear center of the car. • The rows of the same number of passenger seats are on both sides of the aisle.

A rough estimation requested is based on a simple step-wise model. All passengers are initially on a distinct seat, and they can make one of the following moves in each step.

• Passengers on a seat can move to an adjacent seat toward the aisle. Passengers on a seat adjacent to the aisle can move sideways directly to the aisle. • Passengers on the aisle can move backward by one row of seats. If the passenger is in front of the emergency exit, that is, by the rear-most seat rows, he/she can get off the car.

The seat or the aisle position to move to must be empty; either no other passenger is there before the step, or the passenger there empties the seat by moving to another position in the same step. When two or more passengers satisfy the condition for the same position, only one of them can move, keeping the others wait in their original positions.

The leftmost figure of Figure C.1 depicts the seat arrangement of a small car given in Sample Input 1. The car have five rows of seats, two seats each on both sides of the aisle, totaling twenty. The initial positions of seven passengers on board are also shown.

The two other figures of Figure C.1 show possible positions of passengers after the first and the second steps. Passenger movements are indicated by fat arrows. Note that, two of the passengers in the front seat had to wait for a vacancy in the first step, and one in the second row had to wait in the next step.

Your task is to write a program that gives the smallest possible number of steps for all the passengers to get off the car, given the seat arrangement and passengers’ initial positions.

4

Initial After Step 1 After Step 2

Figure C.1. Simple Model

Input

The input consists of a single test case of the following format.

r s p i1 j1 . . . ip jp

Here, r is the number of passenger seat rows, s is the number of seats on each side of the aisle, and p is the number of passengers. They are integers satisfying 1 ≤ r ≤ 500, 1 ≤ s ≤ 500, and 1 ≤ p ≤ 2rs. The following p lines give initial seat positions of the passengers. The k-th line with ik and jk means that the k-th passenger’s seat is in the ik-th seat row and it is the jk-th seat on that row. Here, rows and seats are counted from front to rear and left to right, both starting from one. They satisfy 1 ≤ ik ≤ r and 1 ≤ jk ≤ 2s. Passengers are on distinct seats, that is, ik 6= il or jk 6= jl holds if k 6= l.

Output

The output should be one line containing a single integer, the minimum number of steps required for all the passengers to get off the car.

题意

给出座位，以及人的位置，询问多久人能撤离。。

题解

标算：

用反方向考虑，问几次能使图变成原来的样子。O(nlogn)

假算法：

暴力跑1000次，如果走完的话输出，之后一定每一次出一个人，所以为1000+lft。

O（n*n*1000）

代码

#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
bool b[505][1005];
int main()
{
int r,s,p;
cin>>r>>s>>p;
REP(i,1,p)
{
int x,y;
cin>>x>>y;
if(y<=s) b[x][y-1]=true;
else b[x][y]=true;
}
REP(i,1,1000)
{
if(b[r][s]) b[r][s]=0,p--;
if(p==0)
{
cout<<i;
return 0;
}
for(int c=r; c; c--)
{
if(!b[c][s])
{
if(b[c-1][s]) b[c-1][s]=0,b[c][s]=1;
else if(b[c][s-1]) b[c][s-1]=0,b[c][s]=1;
else if(b[c][s+1]) b[c][s+1]=0,b[c][s]=1;
}
for(int y=s-1; y; y--) if(!b[c][y]&&b[c][y-1]) b[c][y-1]=0,b[c][y]=1;
REP(y,s+1,s*2-1) if(!b[c][y]&&b[c][y+1]) b[c][y+1]=0,b[c][y]=1;
}
}
cout<<1000+p<<endl;
return 0;
}


Problem D Shortest Common Non-Subsequence

题面

Time Limit: 5 seconds

A subsequence of a sequence P is a sequence that can be derived from the original sequence P by picking up some or no elements of P preserving the order. For example, “ICPC” is a subsequence of “MICROPROCESSOR”.

A common subsequence of two sequences is a subsequence of both sequences. The famous longest common subsequence problem is finding the longest of common subsequences of two given sequences.

In this problem, conversely, we consider the shortest common non-subsequence problem: Given two sequences consisting of 0 and 1, your task is to find the shortest sequence also consisting of 0 and 1 that is a subsequence of neither of the two sequences.

Input

The input consists of a single test case with two lines. Both lines are sequences consisting only of 0 and 1. Their lengths are between 1 and 4000, inclusive.

Output

Output in one line the shortest common non-subsequence of two given sequences. If there are two or more such sequences, you should output the lexicographically smallest one. Here, a sequence P is lexicographically smaller than another sequence Q of the same length if there exists k such that P1 = Q1, ..., Pk−1 = Qk−1, and Pk < Qk, where Si is the i-th character of a sequence S.

代码

#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
int l1,l2,f[4005][4005],g1[4005],g2[4005],p1[4005][2],p2[4005][2];
char s1[4005],s2[4005];
int max(int a,int b,int c)
{
return max(a,max(b,c));
}
void print(int i,int j,int len)
{
if(len==1)
{
bool b=false;
REP(k,i,l1) if(s1[k]=='0') b=true;
REP(k,j,l2) if(s2[k]=='0') b=true;
if(b) cout<<1;
else cout<<0;
return;
}
if(i>l1)
{
if(g2[p2[j][0]+1]<len-1)
{
cout<<0;
print(i,p2[j][0]+1,len-1);
}
else
{
cout<<1;
print(i,p2[j][1]+1,len-1);
}
}
else if(j>l2)
{
if(g1[p1[i][0]+1]<len-1)
{
cout<<0;
print(p1[i][0]+1,j,len-1);
}
else
{
cout<<1;
print(p1[i][1]+1,j,len-1);
}
}
else
{
if(max(g1[p1[i][0]+1],g2[p2[j][0]+1],f[p1[i][0]+1][p2[j][0]+1])<len-1)
{
cout<<0;
print(p1[i][0]+1,p2[j][0]+1,len-1);
}
else
{
cout<<1;
print(p1[i][1]+1,p2[j][1]+1,len-1);
}
}
}
int main()
{
scanf("%s %s",s1+1,s2+1);
l1=strlen(s1+1),l2=strlen(s2+1);
p1[l1+1][0]=p1[l1+1][1]=l1+1;
for(int i=l1; i; i--)
{
if(s1[i]=='0')
{
p1[i][0]=i;
p1[i][1]=p1[i+1][1];
}
else
{
p1[i][1]=i;
p1[i][0]=p1[i+1][0];
}
}p2[l2+1][0]=p2[l2+1][1]=l2+1;
for(int i=l2; i; i--)
{
if(s2[i]=='0')
{
p2[i][0]=i;
p2[i][1]=p2[i+1][1];
}
else
{
p2[i][1]=i;
p2[i][0]=p2[i+1][0];
}
}for(int i=l1; i; i--) if(p1[i][0]<=l1&&p1[i][1]<=l1)
g1[i]=min(g1[p1[i][0]+1],g1[p1[i][1]+1])+1;
for(int i=l2; i; i--) if(p2[i][0]<=l2&&p2[i][1]<=l2)
g2[i]=min(g2[p2[i][0]+1],g2[p2[i][1]+1])+1;
for(int i=l1; i; i--)
for(int j=l2; j; j--)
if((p1[i][0]<=l1||p2[j][0]<=l2)&&(p1[i][1]<=l1||p2[j][1]<=l2))
f[i][j]=min(max(g1[p1[i][0]+1],g2[p2[j][0]+1],f[p1[i][0]+1][p2[j][0]+1]),
max(g1[p1[i][1]+1],g2[p2[j][1]+1],f[p1[i][1]+1][p2[j][1]+1]))+1;
print(1,1,f[1][1]+1);
return 0;
}

Problem E Eulerian Flight Tour

Problem G What Goes Up Must Come Down

Time Limit: 2 seconds

Several cards with numbers printed on them are lined up on the table.

We’d like to change their order so that first some are in non-decreasing order of the numbers on them, and the rest are in non-increasing order. For example, (1, 2, 3, 2, 1), (1, 1, 3, 4, 5, 9, 2), and (5, 3, 1) are acceptable orders, but (8, 7, 9) and (5, 3, 5, 3) are not.

To put it formally, with n the number of cards and bi the number printed on the card at the i-th position (1 ≤ i ≤ n) after reordering, there should exist k ∈ {1,...,n} such that (bi ≤ bi+1 ∀i ∈{1,...,k−1}) and (bi ≥ bi+1 ∀i ∈{k,...,n−1}) hold. For reordering, the only operation allowed at a time is to swap the positions of an adjacent card pair. We want to know the minimum number of swaps required to complete the reorder.

Input

The input consists of a single test case of the following format.

n a1 ... an An integer n in the first line is the number of cards (1 ≤ n ≤ 100000). Integers a1 through an in the second line are the numbers printed on the cards, in the order of their original positions (1 ≤ ai ≤ 100000).

Output

Output in a line the minimum number of swaps required to reorder the cards as specified.

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> vec[N];
int n;
namespace Fenwick
{
#define lowbit(i) (i & -i)
ll tr[N];
void add(int p, int v)
{
for (int i = p; i <= N; i += lowbit(i))
tr[i] += v;
}
ll query(int p)
{
ll res = 0;
for (int i = p; i >= 1; i -= lowbit(i))
res += tr[i];
return res;
}
}
ll ans = 0;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++)
{
int x;
cin >> x;
vec[x].push_back(i);
Fenwick::add(i, 1);
}
for (int i = 1; i < N; i ++)
{
if (vec[i].empty()) continue;
for (int j = 0; j < (int) vec[i].size(); j ++)
{
int x = vec[i][j];
Fenwick::add(x, -1);
-- n;
}
for (int j = 0; j < (int) vec[i].size(); j ++)
{
int x = vec[i][j];
ans += min(Fenwick::query(x - 1), n - Fenwick::query(x));
}
}
cout << ans << endl;
return 0;
}


Problem H Four-Coloring

Time Limit: 2 seconds

You are given a planar embedding of a connected graph. Each vertex of the graph corresponds to a distinct point with integer coordinates. Each edge between two vertices corresponds to a straight line segment connecting the two points corresponding to the vertices. As the given embedding is planar, the line segments corresponding to edges do not share any points other than their common endpoints. The given embedding is organized so that inclinations of all the line segments are multiples of 45 degrees. In other words, for two points with coordinates (xu,yu) and (xv,yv) corresponding to vertices u and v with an edge between them, one of xu = xv, yu = yv, or |xu −xv| = |yu −yv| holds.

Your task is to color each vertex in one of the four colors, {1,2,3,4}, so that no two vertices connected by an edge are of the same color. According to the famous four color theorem, such a coloring is always possible. Please find one.

Input

The input consists of a single test case of the following format.

n m x1 y1 . . . xn yn u1 v1 . . . um vm

The first line contains two integers, n and m. n is the number of vertices and m is the number of edges satisfying 3 ≤ n ≤ m ≤ 10000. The vertices are numbered 1 through n. Each of the next n lines contains two integers. Integers on the v-th line, xv (0 ≤ xv ≤ 1000) and yv

(0 ≤ yv ≤ 1000), denote the coordinates of the point corresponding to the vertex v. Vertices correspond to distinct points, i.e., (xu,yu) 6= (xv,yv) holds for u 6= v. Each of the next m lines contains two integers. Integers on the i-th line, ui and vi, with 1 ≤ ui < vi ≤ n, mean that there is an edge connecting two vertices ui and vi.

Output

The output should consist of n lines. The v-th line of the output should contain one integer cv ∈ {1,2,3,4} which means that the vertex v is to be colored cv. The output must satisfy cu 6= cv for every edge connecting u and v in the graph. If there are multiple solutions, you may output any one of them.

#include <bits/stdc++.h>
#define mkp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 10005;
struct point
{
pii loc;
int id;
point(pii _loc, int _id = 0)
{
loc = _loc;
id = _id;
}
bool operator < (point rhs) const
{
return loc == rhs.loc ? id < rhs.id : loc < rhs.loc;
}
};
vector<point> v;
vector<int> g[N];
int n, m;
int col[N];
bool vis[N];
int findCol(int u)
{
memset(vis, 0, sizeof(vis));
for (auto v : g[u])
{
vis[col[v]] = 1;
}
for (int i = 1; i <= 4; i ++) if (!vis[i]) return i;
return 0;
}
void rever(int u, int pre, int now)
{
col[u] = pre;
for (auto v : g[u])
{
if (col[v] == pre) rever(v, now, pre);
}
}
void solve(int u)
{
col[u] = findCol(u);
if (col[u]) return;
for (auto v : g[u])
{
if (!col[v]) continue;
for (int i = 1; i <= 4; i ++)
{
rever(v, i, col[v]);
col[u] = findCol(u);
if (col[u]) return;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int x, y;
cin >> x >> y;
v.push_back(point(mkp(x, y), i));
}
sort(v.begin(), v.end());
for (int i = 1, u, v; i <= m; i ++)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (auto u : v) solve(u.id);
for (int i = 1; i <= n; i ++)
{
cout << col[i] << endl;
}
return 0;
}


Problem K Sixth Sense

Time Limit: 5 seconds

Ms. Future is gifted with precognition. Naturally, she is excellent at some card games since she can correctly foresee every player’s actions, except her own. Today, she accepted a challenge from a reckless gambler Mr. Past. They agreed to play a simple two-player trick-taking card game.

Cards for the game have a number printed on one side, leaving the other side blank making indistinguishable from other cards.

A game starts with the same number, say n, of cards being handed out to both players, without revealing the printed number to the opponent.

A game consists of n tricks. In each trick, both players pull one card out of her/his hand. The player pulling out the card with the larger number takes this trick. Because Ms. Future is extremely good at this game, they have agreed to give tricks to Mr. Past when both pull out cards with the same number. Once a card is used, it can never be used later in the same game. The game continues until all the cards in the hands are used up. The objective of the game is to take as many tricks as possible.

Your mission of this problem is to help Ms. Future by providing a computer program to determine the best playing order of the cards in her hand. Since she has the sixth sense, your program can utilize information that is not available to ordinary people before the game.

Input

The input consists of a single test case of the following format.

n p1 ··· pn f1 ··· fn n in the first line is the number of tricks, which is an integer between 2 and 5000, inclusive. The second line represents the Mr. Past’s playing order of the cards in his hand. In the i-th trick, he will pull out a card with the number pi (1 ≤ i ≤ n). The third line represents the Ms. Future’s hand. fi (1 ≤ i ≤ n) is the number that she will see on the i-th received card from the dealer. Every number in the second or third line is an integer between 1 and 10000, inclusive. These lines may have duplicate numbers.

Output

The output should be a single line containing n integers a1 ··· an separated by a space, where ai (1 ≤ i ≤ n) is the number on the card she should play at the i-th trick for maximizing the number of taken tricks. If there are two or more such sequences of numbers, output the lexicographically greatest one among them.

代码

#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
int i,n,p[5005],f[5005],tmp[5005];
bool vis[5005];
int cal(int l,int cnt,int w)
{
bool c[5005]= {0};
c[w]=true;
int ret=0,pt=1;
REP(j,l,n)
{
while(pt<=n-i+1&&(c[pt]||tmp[j]>=f[pt])) pt++;
if(pt<=n-i+1) ret++,c[pt]=true;
}
return ret;
}
int main()
{
cin>>n;
REP(i,1,n) cin>>p[i];
REP(i,1,n) cin>>f[i];
sort(f+1,f+1+n);
memcpy(tmp,p,sizeof p);
sort(tmp+1,tmp+1+n);
int ans=cal(1,n,0),pre=0;
for(i=1; i<=n; i++)
{
REP(j,i+1,n) tmp[j]=p[j];
sort(tmp+i+1,tmp+1+n);
int w=1;
while(w<=n-i+1&&f[w]<=p[i]) w++;
if(w<=n-i+1)
{
int l=w,r=n-i+1;
while(l<=r)
{
int m=l+r>>1;
if(pre+1+cal(i+1,n-i+1,m)==ans) l=m+1;
else r=m-1;
}
if(f[r]>p[i])
{
cout<<f[r]<<' ';
REP(j,r,n-i) f[j]=f[j+1];
pre++;
continue;
}
}
int l=1,r=w-1;
while(l<=r)
{
int m=l+r>>1;
if(pre+cal(i+1,n-i+1,m)==ans) l=m+1;
else r=m-1;
}
cout<<f[r]<<' ';
REP(j,r,n-i) f[j]=f[j+1];
}
return 0;
}