纪念自己第一次打 AtCoder OUO
HAPPY Studying OvO
因为自己找不来比赛，就到处乱搞，看着 $Atcoder$ 有个 $AtCoder ~Beginner~ Contest$(初学者比赛) 我就（…………2333），然后不知道为什么进来 $AtCoder ~Regular~Contest 103$ (常规比赛 ， …… 看不懂英文就乱点了 QAQ)
放个题目链接
QAQ ARC103
实际上比赛的时候因为完全看不懂题目，写完第一题之后看着后面三题样例看来一个多小时 QwQ，@-@ = =
First ./ \ / \ / \ /
问题陈述
当满足以下条件时，序列 $a_1,a_2,…,a_n$被称为/ \ / \ / \ / ($2<=n <=10^5,1<=v_i$）
1. 对于每个 $i=1,2,3,..n-2,,a_i=a_i+2$
2. 序列中只有两个不同的数字。
给出序列 $v_1,v_2,…,v_n$其长度为偶数。我们想通过替换它的一些元素来制作这个序列/ \ / \ / \ /。找到需要替换的最小元素数。
样例 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 read(){
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[])
{
n=read();
fors(i,1,n) {
a[i]=read();
++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;
}
下面的题还是用原文吧，毕竟我用的网页翻译，翻出来惨不忍睹，英语好的大佬自己应该看得懂。（还是要学好英语 QAQ）
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 read(){
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[])
{
n=read();
fors(i,1,n){
a[i]=read(),b[i]=read();
((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$
S is a string of length n consisting of 0 and 1.
Sample Input 1
1111
Sample Output 1
-1
It is impossible to have a connected component of size n after removing one edge from a tree with n vertices.
Sample Input 2
1110
Sample Output 2
1 2
2 3
3 4
If Edge 1 or Edge 3 is removed, we will have a connected component of size 1 and another of size 3. If Edge 2 is removed, we will have two connected components, each of size 2.
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 read(){
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
Problem Statement
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
Output
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
The tree shown below satisfies the conditions.
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 read(){
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()
{
ll n=read();
maps.clear();
fors(i,1,n){
d[i]=read();
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;
}
2 条评论
XZYQvQ · 2018年10月1日 4:55 下午
Orz atcoder 我题目都看不懂，您肽聚了
B_Z_B_Y · 2018年10月1日 5:10 下午
比赛我都是看网页翻译的，但那个太烂，题目长的根本理解不了，而且我还是结束后看别人代码推出题意的。我 tcl。QAQ