纪念自己第一次打 AtCoder OUO

HAPPY Studying OvO

First ./ \ / \ / \ /

问题陈述

1. 对于每个 $i=1,2,3,..n-2,,a_i=a_i+2$
2. 序列中只有两个不同的数字。

样例 1：

4
3 1 3 2

1


样例 2：

6
105 119 105 119 105 119

0


样例 3：

4
1 1 1 1

2


这么简单的题我做了半小时，别人 dalao 只用了 10min 不到 Orz

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
using namespace std;
#define fors(i,a,b) for(int i=(a);i=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
const int maxn=1e6+7;
typedef long long ll;

int s=0,f=1;
char c=getchar();
while(c<'9' || c>'0') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&& c<='9') {s=s*10+c-48;c=getchar();}
return s*f;
}
void write(int x){
if(x9) write(x/10);
putchar(x%10+48);
}
int n,a[maxn],cnt[2][maxn],mx1,mx11,mx2,mx22,n1,n2;
int main(int argc, char const *argv[])
{

fors(i,1,n) {
++cnt[i%2][a[i]];//用一个二维桶储存，cnt[0] 存的是偶数下标，cnt[1] 存的是奇数下标
}
fors(i, 1, maxn){//分别对奇数下标和偶数下标 从 1~100000 查询最大重复数的次数。
if(cnt[0][i] > mx1){
n1 = i;//n1 代表那个出现次数最多的众数
mx11 = mx1;//mx11 存的是出现次数第二多的众数的个数
mx1 = cnt[0][i];//mx1 存的是出现次数第一多的众数的个数
}
else if(cnt[0][i] > mx11){
mx11 = cnt[0][i];
}

if(cnt[1][i] > mx2){//和上述相同
n2 = i;
mx22 = mx2;
mx2 = cnt[1][i];
}
else if(cnt[1][i] > mx22){
mx22 = cnt[1][i];
}
}
//如果奇数和偶数下标的 n1 == n2 就采用第二大的众数个数
if(n1 == n2){
int mx = max(mx1 + mx22, mx2 + mx11);
write(n - mx);
}
//否则直接相减
else write(n/2-mx1 + n/2-mx2);
return 0;
}


Second. D – Robot Arms

Problem Statement

Snuke is introducing a robot arm with the following properties to his factory:

1.The robot arm consists of m sections and m+1 joints. The sections are numbered 1, 2, …, m, and the joints are numbered 0, 1, …, m. Section i connects Joint i−1 and Joint i. The length of Section i is di.

2.For each section, its mode can be specified individually. There are four modes: L, R, D and U. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint i will be determined as follows (we denote its coordinates as (xi,yi)):
(x0,y0)=(0,0).

3.If the mode of Section i is L, $(x_i,y_i) = (x_(i-1) -d_i,y_(i-1)$.

4.If the mode of Section i is R, $(x_i,y_i)=(x_(i-1)+d_i,y_(i-1))$.

5.If the mode of Section i is D, $(x_i,y_i) = (x_(i-1),y_(i-1)- d_i)$.

6.If the mode of Section i is U, $(x_i,y_i) =(x_(i-1),y_(i-1)+d_i)$.

7.Snuke would like to introduce a robot arm so that the position of Joint m can be matched with all of the N points $(X_1,Y_1),(X_2,Y_2),…,(X_N,Y_N)$by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint m to each point $(Xj,Yj)$.

Constraints

All values in input are integers.

$1≤N≤1000$

$-10^9≤Xi≤10^9$

$-10^9≤Yi≤10^9$

Input:

N
X1 Y1
X2 Y2
:
XN YN

output:

m
d1 d2 … dm
w1
w2
:
wN


If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print -1.

m and di are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, 1≤m≤40 and 1≤di≤10^12 must hold. Also, m and di must all be integers.

wj is a string of length m that represents the way to bring Joint m of the robot arm to point (Xj,Yj). The i-th character of wj should be one of the letters L, R, D and U, representing the mode of Section i.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
const int maxn=1e6+7;
typedef long long ll;
const int inf=1<<25;
int s=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-48;c=getchar();}
return s*f;
}
void write(int x){
if(x<0) {putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+48);
}

int abs(int x){
return x < 0 ? -x : x;
}
int a[maxn],b[maxn],n,m,c,flag;
char s[45];

int main(int argc, char const *argv[])
{
fors(i,1,n){
((a[i]+b[i]) & 1) ?  ++c : --c;
}

if(abs(c) != n) return puts("-1"),0;

m=31 + (c < 0);

write(m),putchar(10);

fors(i,0,30){
printf("%d ", 1<<i );
}

if(c < 0) putchar('1');

putchar(10);

fors(i,1,n){
int x=a[i],y=b[i];//坐标
if(c < 0) s[31]='R' , --x;
flag = 0;
ford(j,30,0){//以 flag 的标记，判断连接的部件
if(abs(x) < abs(y)) swap(x,y),flag ^= 1;
if(x > 0 ) x-= 1<<j ,s[j] = flag ?  'U' : 'R';
else x+= 1 << j , s[j] = flag ? 'D' : 'L';
}

puts(s);//将这个一串全部输出

}

return 0;
}


Second. E – Tr/ee

Problem Statement

You are given a string s of length n. Does a tree with n vertices that satisfies the following conditions exist?

The vertices are numbered 1,2,…,n.
The edges are numbered 1,2,…,n−1, and Edge i connects Vertex ui and vi.
If the i-th character in s is 1, we can have a connected component of size i by removing one edge from the tree.
If the i-th character in s is 0, we cannot have a connected component of size i by removing any one edge from the tree.
If such a tree exists, construct one such tree.

Constraints

$2≤n≤10^5$

Sample Input 1

1111

Sample Output 1

-1

Sample Input 2

1110

Sample Output 2

1 2
2 3
3 4


Sample Input 3

1010

Sample Output 3

1 2
1 3
1 4


Removing any edge will result in a connected component of size 1 and another of size 3.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
const int maxn=1e6+7;
typedef long long ll;
const int inf=1<<25;
int s=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-48;c=getchar();}
return s*f;
}
void write(int x){
if(x<0) {putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+48);
}

int abs(int x){
return x < 0 ? -x : x;
}
string s;
int main(int argc, char const *argv[])
{

cin>>s;
int len=s.length();
int flag=1;

if(s[0] != '1' || s[len-1] != '0') flag=0;
//有 n 个顶点的树中移除一个边之后，不可能具有大小为 n 的连通分量。
int r=len-2;//注意从倒数第二个开始判断
fors(i,0,r){
if(s[i]!=s[r-i]) flag=0;
}
if(!flag) {
puts("-1");
}
else {
int x=1;
fors(i,0,len-2){
write(x),putchar(' '),write(i+2),putchar(10);
if(s[i] == '1' ) x=i+2;
}
}
return 0;
}


Four.Distance Sums

You are given a sequence D1,D2,…,DN of length N. The values of Di are all distinct. Does a tree with N vertices that satisfies the following conditions exist?

The vertices are numbered 1,2,…,N.
The edges are numbered 1,2,…,N−1, and Edge i connects Vertex ui and vi.
For each vertex i, the sum of the distances from i to the other vertices is Di, assuming that the length of each edge is 1.
If such a tree exists, construct one such tree.

Constraints

$2≤N≤100000$

$1≤D_i≤ 10 ^(12)$

$D_i$ are all distinct.

Input is given from Standard Input in the following format:

N
D1
D2
:
DN


If a tree with n vertices that satisfies the conditions does not exist, print -1.

If a tree with n vertices that satisfies the conditions exist, print n−1 lines. The i-th line should contain ui and vi with a space in between. If there are multiple trees that satisfy the conditions, any such tree will be accepted.

Sample Input 1

7
10
15
13
18
11
14
19


Sample Output 1

1 2
1 3
1 5
3 4
5 6
6 7


Sample Input 2

2
1
2


Sample Output 2

-1


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
#define abs(x) ((x) < 0 ? -(x) : (x))
const int maxn=1e6+7;
typedef long long ll;
const int inf=1<<25;
ll s=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-48;c=getchar();}
return s*f;
}
void write(int x){
if(x<0) {putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+48);
}
int tree[101010];
ll d[101010];
int siz[101010],fa[101010];
int cmp(int x,int y){
return d[x] < d[y];
}
map<ll,int> maps;
int main()
{
maps.clear();
fors(i,1,n){
siz[i]=1;
maps[d[i]]=i;
tree[i]=i;
}
sort(tree+1,tree+n+1,cmp);//按 d 排序
for(int i=n;i>1;i--){
fa[tree[i]]=maps[ d[tree[i]]+ 2*siz[tree[i]] -n ];//记录符合题意的节点
if(!fa[tree[i]]){
printf("-1");
return 0;
}
siz[fa[tree[i]]]+=siz[tree[i]];
}
fors(i,2,n)
d[tree[1]]-=siz[tree[i]];
if(d[tree[1]]){
printf("-1");
return 0;
}
fors(i,2,n)
printf("%d %d\n",fa[tree[i]],tree[i]);
return 0;
}


B_Z_B_Y

Let us go go go！！！！！！ 　☆ *　. 　☆ 　　. ∧＿∧　∩　* ☆ * ☆ ( ・∀・)/ . 　. ⊂　　 ノ* ☆ ☆ * (つ ノ .☆ 　　 (ノ

2 条评论

XZYQvQ · 2018年10月1日 4:55 下午

Orz atcoder 我题目都看不懂，您肽聚了

B_Z_B_Y · 2018年10月1日 5:10 下午

比赛我都是看网页翻译的，但那个太烂，题目长的根本理解不了，而且我还是结束后看别人代码推出题意的。我 tcl。QAQ