纪念自己第一次打 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.

s

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;
}
分类: 文章

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

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注