Codeforces Round #532 (Div. 2) 解题报告

77 阅读 0 评论 51 点赞

我是靠谱客的博主害怕羽毛，最近开发中收集的这篇文章主要介绍Codeforces Round #532 (Div. 2) 解题报告，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Codeforces Round #532 (Div. 2)

A. Roman and Browser

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
This morning, Roman woke up and opened the browser with n opened tabs numbered from 1 to n. There are two kinds of tabs: those with the information required for the test and those with social network sites. Roman decided that there are too many tabs open so he wants to close some of them.

He decided to accomplish this by closing every k-th (2≤k≤n−1) tab. Only then he will decide whether he wants to study for the test or to chat on the social networks. Formally, Roman will choose one tab (let its number be b) and then close all tabs with numbers c=b+i⋅k that satisfy the following condition: 1≤c≤n and i is an integer (it may be positive, negative or zero).

For example, if k=3, n=14 and Roman chooses b=8, then he will close tabs with numbers 2, 5, 8, 11 and 14.

After closing the tabs Roman will calculate the amount of remaining tabs with the information for the test (let's denote it e) and the amount of remaining social network tabs (s). Help Roman to calculate the maximal absolute value of the difference of those values |e−s| so that it would be easy to decide what to do next.

Input
The first line contains two integers n and k (2≤k<n≤100) — the amount of tabs opened currently and the distance between the tabs closed.

The second line consists of n integers, each of them equal either to 1 or to −1. The i-th integer denotes the type of the i-th tab: if it is equal to 1, this tab contains information for the test, and if it is equal to −1, it's a social network tab.

Output
Output a single integer — the maximum absolute difference between the amounts of remaining tabs of different types |e−s|.

Examples
inputCopy
4 2
1 1 -1 1
outputCopy
2
inputCopy
14 3
-1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 1
outputCopy
9
Note
In the first example we can choose b=1 or b=3. We will delete then one tab of each type and the remaining tabs are then all contain test information. Thus, e=2 and s=0 and |e−s|=2.

In the second example, on the contrary, we can leave opened only tabs that have social networks opened in them.

-----------------------------------------------------------------------------------------

B. Build a Contest

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Arkady coordinates rounds on some not really famous competitive programming platform. Each round features n problems of distinct difficulty, the difficulties are numbered from 1 to n.

To hold a round Arkady needs n new (not used previously) problems, one for each difficulty. As for now, Arkady creates all the problems himself, but unfortunately, he can't just create a problem of a desired difficulty. Instead, when he creates a problem, he evaluates its difficulty from 1 to n and puts it into the problems pool.

At each moment when Arkady can choose a set of n new problems of distinct difficulties from the pool, he holds a round with these problems and removes them from the pool. Arkady always creates one problem at a time, so if he can hold a round after creating a problem, he immediately does it.

You are given a sequence of problems' difficulties in the order Arkady created them. For each problem, determine whether Arkady held the round right after creating this problem, or not. Initially the problems pool is empty.

Input
The first line contains two integers n and m (1≤n,m≤105) — the number of difficulty levels and the number of problems Arkady created.

The second line contains m integers a1,a2,…,am (1≤ai≤n) — the problems' difficulties in the order Arkady created them.

Output
Print a line containing m digits. The i-th digit should be 1 if Arkady held the round after creation of the i-th problem, and 0 otherwise.

Examples
inputCopy
3 11
2 3 1 2 2 2 3 2 2 3 1
outputCopy
00100000001
inputCopy
4 8
4 1 3 3 2 3 3 3
outputCopy
00001000
Note
In the first example Arkady held the round after the first three problems, because they are of distinct difficulties, and then only after the last problem.

-----------------------------------------------------------------------------------------
C. NN and the Optical Illusion

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
NN is an experienced internet user and that means he spends a lot of time on the social media. Once he found the following image on the Net, which asked him to compare the sizes of inner circles:


It turned out that the circles are equal. NN was very surprised by this fact, so he decided to create a similar picture himself.

He managed to calculate the number of outer circles n and the radius of the inner circle r. NN thinks that, using this information, you can exactly determine the radius of the outer circles R so that the inner circle touches all of the outer ones externally and each pair of neighboring outer circles also touches each other. While NN tried very hard to guess the required radius, he didn't manage to do that.

Help NN find the required radius for building the required picture.

Input
The first and the only line of the input file contains two numbers n and r (3≤n≤100, 1≤r≤100) — the number of the outer circles and the radius of the inner circle respectively.

Output
Output a single number R — the radius of the outer circle required for building the required picture.

Your answer will be accepted if its relative or absolute error does not exceed 10−6.

Formally, if your answer is a and the jury's answer is b. Your answer is accepted if and only when |a−b|max(1,|b|)≤10−6.

Examples
inputCopy
3 1
outputCopy
6.4641016
inputCopy
6 1
outputCopy
1.0000000
inputCopy
100 100
outputCopy
3.2429391

-----------------------------------------------------------------------------------------
D. Dasha and Chess

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
This is an interactive task.

Dasha and NN like playing chess. While playing a match they decided that normal chess isn't interesting enough for them, so they invented a game described below.

There are 666 black rooks and 1 white king on the chess board of size 999×999. The white king wins if he gets checked by rook, or, in other words, if he moves onto the square which shares either a row or column with a black rook.

The sides take turns, starting with white. NN plays as a white king and on each of his turns he moves a king to one of the squares that are adjacent to his current position either by side or diagonally, or, formally, if the king was on the square (x,y), it can move to the square (nx,ny) if and only max(|nx−x|,|ny−y|)=1 , 1≤nx,ny≤999. NN is also forbidden from moving onto the squares occupied with black rooks, however, he can move onto the same row or column as a black rook.

Dasha, however, neglects playing by the chess rules, and instead of moving rooks normally she moves one of her rooks on any space devoid of other chess pieces. It is also possible that the rook would move onto the same square it was before and the position wouldn't change. However, she can't move the rook on the same row or column with the king.

Each player makes 2000 turns, if the white king wasn't checked by a black rook during those turns, black wins.

NN doesn't like losing, but thinks the task is too difficult for him, so he asks you to write a program that will always win playing for the white king. Note that Dasha can see your king and play depending on its position.

Input
In the beginning your program will receive 667 lines from input. Each line contains two integers x and y (1≤x,y≤999) — the piece's coordinates. The first line contains the coordinates of the king and the next 666 contain the coordinates of the rooks. The first coordinate denotes the number of the row where the piece is located, the second denotes the column. It is guaranteed that initially the king isn't in check and that all pieces occupy different squares.

Output
After getting king checked, you program should terminate immediately without printing anything extra.

Interaction
To make a move with the king, output two integers x and y (1≤x,y≤999) — the square to which the king would be moved. The king cannot move onto the square already occupied by a rook. It is guaranteed that the king would always have a valid move.

After each of your turns read the rook's turn in the following format: a single line containing three integers k, x and y (1≤k≤666, 1≤xi,yi≤999) — the number of the rook that would move and the square it would move to. It is guaranteed that the rook wouldn't move to a square already occupied by another chess piece, but it can move onto the square where it was before the turn so that its position wouldn't change. It is guaranteed that the move does not put your king into a check. If your king got in check, all three integers would be equal to −1 and in that case your program should terminate immediately.

After printing your turn do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see documentation for other languages.
Answer "0 0 0" instead of a correct answer means that you made an invalid query. Exit immediately after receiving "0 0 0" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks are not allowed for this problem.

Example
inputCopy
999 999
1 1
1 2
2 1
2 2
1 3
2 3
<...>
26 13
26 14
26 15
26 16

1 700 800

2 1 2

<...>

-1 -1 -1
outputCopy











999 998

999 997

<...>

999 26
Note
The example is trimmed. The full initial positions of the rooks in the first test are available at https://pastebin.com/qQCTXgKP. It is not guaranteed that they will behave as in the example.

-----------------------------------------------------------------------------------------
E. Andrew and Taxi

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Andrew prefers taxi to other means of transport, but recently most taxi drivers have been acting inappropriately. In order to earn more money, taxi drivers started to drive in circles. Roads in Andrew's city are one-way, and people are not necessary able to travel from one part to another, but it pales in comparison to insidious taxi drivers.

The mayor of the city decided to change the direction of certain roads so that the taxi drivers wouldn't be able to increase the cost of the trip endlessly. More formally, if the taxi driver is on a certain crossroads, they wouldn't be able to reach it again if he performs a nonzero trip.

Traffic controllers are needed in order to change the direction the road goes. For every road it is known how many traffic controllers are needed to change the direction of the road to the opposite one. It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads.

You need to calculate the minimum number of traffic controllers that you need to hire to perform the task and the list of the roads that need to be reversed.

Input
The first line contains two integers n and m (2≤n≤100000, 1≤m≤100000) — the number of crossroads and the number of roads in the city, respectively.

Each of the following m lines contain three integers ui, vi and ci (1≤ui,vi≤n, 1≤ci≤109, ui≠vi) — the crossroads the road starts at, the crossroads the road ends at and the number of traffic controllers required to reverse this road.

Output
In the first line output two integers the minimal amount of traffic controllers required to complete the task and amount of roads k which should be reversed. k should not be minimized.

In the next line output k integers separated by spaces — numbers of roads, the directions of which should be reversed. The roads are numerated from 1 in the order they are written in the input. If there are many solutions, print any of them.

Examples
inputCopy
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
outputCopy
2 2
1 3 
inputCopy
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3
outputCopy
3 3
3 4 7 
Note
There are two simple cycles in the first example: 1→5→2→1 and 2→3→4→5→2. One traffic controller can only reverse the road 2→1 and he can't destroy the second cycle by himself. Two traffic controllers can reverse roads 2→1 and 2→3 which would satisfy the condition.

In the second example one traffic controller can't destroy the cycle 1→3→2→1. With the help of three controllers we can, for example, reverse roads 1→3 ,2→4, 1→5.

-----------------------------------------------------------------------------------------
F. Ivan and Burgers

time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Ivan loves burgers and spending money. There are n burger joints on the street where Ivan lives. Ivan has q friends, and the i-th friend suggested to meet at the joint li and walk to the joint ri (li≤ri). While strolling with the i-th friend Ivan can visit all joints x which satisfy li≤x≤ri.

For each joint Ivan knows the cost of the most expensive burger in it, it costs ci burles. Ivan wants to visit some subset of joints on his way, in each of them he will buy the most expensive burger and spend the most money. But there is a small issue: his card broke and instead of charging him for purchases, the amount of money on it changes as follows.

If Ivan had d burles before the purchase and he spent c burles at the joint, then after the purchase he would have d⊕c burles, where ⊕ denotes the bitwise XOR operation.

Currently Ivan has 22100−1 burles and he wants to go out for a walk. Help him to determine the maximal amount of burles he can spend if he goes for a walk with the friend i. The amount of burles he spends is defined as the difference between the initial amount on his account and the final account.

Input
The first line contains one integer n (1≤n≤500000) — the number of burger shops.

The next line contains n integers c1,c2,…,cn (0≤ci≤106), where ci — the cost of the most expensive burger in the burger joint i.

The third line contains one integer q (1≤q≤500000) — the number of Ivan's friends.

Each of the next q lines contain two integers li and ri (1≤li≤ri≤n) — pairs of numbers of burger shops between which Ivan will walk.

Output
Output q lines, i-th of which containing the maximum amount of money Ivan can spend with the friend i.

Examples
inputCopy
4
7 2 3 4
3
1 4
2 3
1 3
outputCopy
7
3
7
inputCopy
5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
outputCopy
12
14
27
27
31
14
25
26
30
23
26
29
13
13
7
Note
In the first test, in order to spend the maximum amount of money with the first and third friends, Ivan just needs to go into the first burger. With a second friend, Ivan just go to the third burger.

In the second test for a third friend (who is going to walk from the first to the third burger), there are only 8 options to spend money — 0, 12, 14, 23, 12⊕14=2, 14⊕23=25, 12⊕23=27, 12⊕14⊕23=20. The maximum amount of money it turns out to spend, if you go to the first and third burger — 12⊕23=27.

题意描述：

A. 去掉一个等差序列，问你剩下的1和-1的差值的和

//A

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,ans,flag,temp,countt;
    int a[100010],c[100010];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        ans=0;
        flag=1;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        for(int i=0;i<=k;i++)
        {
            memset(c,0,sizeof(c));
            for(int j=i;j<=n;j+=k)
                c[j]=1;
            temp=0;
            countt=0;
            for(int j=1;j<=n;j++)
            if(!c[j]&&a[j]==1)
                temp++;
            else
                if(!c[j])
                   countt++;
            ans=max(ans,abs(temp-countt));
        }
        printf("%dn",ans);
    }
    return 0;
}

B.给定一个k值和n个数，如果k个数已经全出现过一次了，就输出1，这是一个循环，然后全置为0

如果没有，就输出0

#include<bits/stdc++.h>
using namespace std;
int a[2000010],c[2000010],b[2000010];
char d[2000010];
int main()
{
    int k,n,ans,flag,tmp;
    scanf("%d%d",&k,&n);
    {
        ans=0;
        flag=1;
        memset(c,0,sizeof(c));
        memset(b,0,sizeof(b));
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            d[i]='0';
            c[a[i]]++;
            b[c[a[i]]]++;
            if(b[c[a[i]]]==k)
            {
                d[i]='1';
            }
            cout<<d[i];
        }
        cout<<endl;
    }
    return 0;
}

C. 给你中间一个圆的半径和它被n个等半径的圆（与前面圆的半径关系不一定）所完全包围，问你外面圆的半径是多少。

R/( R+ r)= sin(1/n*π) 因为外面圆都是相切的，所以能构造出一个直角三角形来，出来上面的式子

#include<bits/stdc++.h>
using namespace std;
#define pi 3.1415926535893238
double x,y,a,b;
int main()
{
  scanf("%lf%lf",&x,&y);
  a=sin(1.0/x*pi);
  b=y*a/(1.0-a);
  printf("%.7fn",b);
  return 0;
}

白:八连通一次一格;
黑:瞬间移动
要求任意棋子移动不能移动到有棋子的格子上
要求白走到黑的同行或者同列,白胜
我们扮演白,黑不会瞬间移动到我们的同行同列上

棋盘:999*999
黑666个
666/4=166…2;
所以平均下来将棋盘平均分四块
在平均分的这种最差的情况下
其中三块黑棋数量和最多有167+167+166=500;
所以先将白走到500,500也就是棋盘中央
然后往黑旗数量最少的那块的反对角线走即可必胜.
自己画画图,将黑的同行同列画出就是有点像扫描线一样扫.
其实是扫四分之三的区域

#include<bits/stdc++.h>
using namespace std;typedef long long ll;typedef pair<int,int>pii;
#define fi first
#define sc second
#define sz(a) ((int)(a).size())
#define f(i,a,b) for(int i=a;i<b;++i)
#define ff(i,a,b) for(int i=a;i<=b;++i)
#define file freopen("in.txt","r",stdin)
#define mem(a,b) memset(a,b,sizeof(a))
/*********************************************/
const int N=1e3+5;
const int m=500; 
int x,y,xx[N],yy[N],x2,y2,now,tox,toy;
int mp[N][N];
struct node {
	int num;
	int w;
}hh[4];
bool cmp(node a,node b) {return a.num<b.num;}
void tosw(int x1,int y1) {
	while(x!=x1||y!=y1) {
		if(y<y1) y++;else y--;
		if(x<x1&&mp[x+1][y]==0) x++;
		else if(x>x1&&mp[x-1][y]==0) x--;
		cout << x << ' ' << y << endl;
		cin >> now >> x2 >> y2;
		if(now<0) exit(0);
		mp[xx[now]][yy[now]]=0;
		xx[now]=x2;yy[now]=y2;
		mp[x2][y2]=1;
	}
}
int main() {
	cin >> x >> y;
	ff(i,1,666) {cin >> xx[i] >> yy[i];mp[xx[i]][yy[i]]=1;}
	tosw(m,m);
	ff(i,0,3) hh[i].w=i;
	ff(i,1,999) ff(j,1,999) if(mp[i][j]) {
		if(i<m&&j<m)	hh[0].num++;
		else if(i<m&&j>m) hh[1].num++;
		else if(i>m&&j<m) hh[2].num++;
		else hh[3].num++;
	}
	sort(hh,hh+4,cmp);
	int minn=hh[0].w;
	if(minn==0) {tox=999;toy=999;}
	else if(minn==1) {tox=999;toy=1;}
	else if(minn==2) {tox=1;toy=999;}
	else {tox=1;toy=1;};
	tosw(tox,toy);
	return 0;
}
--------------------- 
原文：https://blog.csdn.net/HananiChen/article/details/86473015

题意
给你一个图1-n标号，m条有向边。
每条有向边有一个权值，代表翻转其方向所需代价。
求使得图变成无环图，翻转边权的最大值最小。

思路
二分答案，判断权值大于答案的边集是否能成环，如果不能说明答案可以再小点，否则答案可以大点。
关键是翻转哪些边比较难想，第一次感受到拓扑排序，排序二字用处。
按拓扑排序的顺序，给每个点从小到大赋权，最后判断如果起点权值大于终点权值则需要翻转。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int sum, in[100005], top[100005];
vector <int> e[100005], path;

struct Node
{
    int u, v, w;
}data[100005];

int f(int mid)
{
    sum = 0;
    for(int i = 1; i <= n; ++i) e[i].clear();
    memset(in,0,sizeof(in));
    for(int i = 1; i <= m; ++i)
    {
        if(data[i].w > mid)
        {
            e[data[i].u].push_back(data[i].v);
            ++in[data[i].v];
        }
    }
    queue<int> q;
    for(int i = 1; i <= n; ++i) if(!in[i]) q.push(i), top[i] = ++sum;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v : e[u])
        {
            --in[v];
            if(!in[v]) q.push(v), top[v] = ++sum;
        }
    }

    for(int i = 1; i <= n; ++i) if(in[i]) return 0;
    return 1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i) scanf("%d%d%d",&data[i].u,&data[i].v,&data[i].w);
    int l = 0, r = 1e9, mid, ans;
    while(l <= r)
    {
        mid = (l+r) >> 1;
        if(f(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }
    f(ans); 
    // 每个点top都有值，且必定能够通过翻转某些边得到当前top值
    for(int i = 1; i <= m; ++i) if(data[i].w <= ans && top[data[i].u] > top[data[i].v]) path.push_back(i);

    printf("%d %dn",ans,path.size());
    for(auto i : path) printf("%d ",i);
    return 0;
}

给定N个数，Q次询问，求区间最大异或和。

我们考虑离线，把所有询问按右端点排序，然后从左到有处理询问，对于当前询问[L,R]；我们把[1,R]所有的数加入线性基，关键是对于每一位，我们保留其为位置，这里肯定是贪心地保留越后面的位置越优。那么查询的时候，如果一个线性基里的数位置>=L，则可以考虑更新答案。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=500010;
struct in{
    int l,r,id;
    friend bool operator< (in w,in v){ return w.r<v.r;}
}s[maxn];
int N,Q,ans[maxn],a[maxn],p[21],pos[21];
void add(int x,int id)
{
    rep2(i,20,0)
      if(x&(1<<i)){
          if(!p[i]){
              p[i]=x; pos[i]=id;
              return ;
        }
        if(pos[i]<id) swap(p[i],x),swap(pos[i],id);
        x^=p[i];
    }
}
int query(int id)
{
    int res=0;
    rep2(i,20,0) if(pos[i]>=id&&(res^p[i])>res) res^=p[i];
    return res;
}
int main()
{
    scanf("%d",&N);
    rep(i,1,N) scanf("%d",&a[i]);
    scanf("%d",&Q);
    rep(i,1,Q) scanf("%d%d",&s[i].l,&s[i].r),s[i].id=i;
    sort(s+1,s+Q+1); int L=1;
    rep(i,1,Q){
          while(L<=s[i].r&&L<=N) add(a[L],L),++L;
          ans[s[i].id]=query(s[i].l);
    }
    rep(i,1,Q) printf("%dn",ans[i]);
    return 0;
}

在线的做法，我们纪录一个前缀和线性基，任然保留最大的位置。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=500010;
int p[maxn][21],pos[maxn][21];
int main()
{
    int N,Q,L,R,x;
    scanf("%d",&N);
    rep(i,1,N) {
        rep(j,0,20) p[i][j]=p[i-1][j],pos[i][j]=pos[i-1][j];
        scanf("%d",&x); int ti=i;
        rep2(j,20,0){
            if(x&(1<<j)){
                if(!p[i][j]) { p[i][j]=x; pos[i][j]=ti; break; }
                if(pos[i][j]<ti) swap(p[i][j],x),swap(pos[i][j],ti);
                x^=p[i][j];
            }
        }
    }
    scanf("%d",&Q);
    rep(i,1,Q) {
        scanf("%d%d",&L,&R);
        int res=0;
        rep2(j,20,0) if(pos[R][j]>=L&&(res^p[R][j])>res) res^=p[R][j];
        printf("%dn",res);
    }
    return 0;
}

整场比赛更新完成