首页 > 其他分享 >2020-2021 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals)

2020-2021 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals)

时间：2024-01-24 19:59:57浏览次数：21  
标签：case std North Northern puts Contest int ITMO break

Preface

最近事情挺多积压了三天没训练，本来计划着去补CF的题，但后面还是溜去写WA2杂谈了

今天重归训练结果碰上超级毒瘤场，2h30min9题后剩下题目都难得飞起，最后还是靠徐神大力切了L题（我早就提前下班了）

评价是这就是Russia场的威力吗，后面的Hard题是一点不可做啊

A. Archivist

纯签到

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int y; scanf("%d",&y);
	switch (y)
	{
		case 1995:
			puts("ITMO"); break;
		case 1996:
			puts("SPbSU"); break;
		case 1997:
			puts("SPbSU"); break;
		case 1998:
			puts("ITMO"); break;
		case 1999:
			puts("ITMO"); break;
		case 2000:
			puts("SPbSU"); break;
		case 2001:
			puts("ITMO"); break;
		case 2002:
			puts("ITMO"); break;
		case 2003:
			puts("ITMO"); break;
		case 2004:
			puts("ITMO"); break;
		case 2005:
			puts("ITMO"); break;
		case 2006:
			puts("PetrSU, ITMO"); break;
		case 2007:
			puts("SPbSU"); break;
		case 2008:
			puts("SPbSU"); break;
		case 2009:
			puts("ITMO"); break;
		case 2010:
			puts("ITMO"); break;
		case 2011:
			puts("ITMO"); break;
		case 2012:
			puts("ITMO"); break;
		case 2013:
			puts("SPbSU"); break;
		case 2014:
			puts("ITMO"); break;
		case 2015:
			puts("ITMO"); break;
		case 2016:
			puts("ITMO"); break;
		case 2017:
			puts("ITMO"); break;
		case 2018:
			puts("SPbSU"); break;
		case 2019:
			puts("ITMO"); break;
	}
	return 0;
}

B. Bicycle

徐神开场写的签到，我没看题目

a = int(input())
x = int(input())
b = int(input())
y = int(input())
a = [a, b]
x = [x, y]
b = [30, 45]

T = int(input())

ans = []

for i in [0, 1]:
    upd = a[i]
    if T >= b[i]:
        upd += (T - b[i]) * x[i] * 21
    ans += [upd]

print("%d %d" % (ans[0], ans[1]))

C. Corrupted Sort

ORZ徐神，鸡尾酒排序秒了

考虑如果我们已经得到了一个有序的数组，对其随机交换两项后，怎样在\(2n\)步之内还原数组

做法是先从前往后冒泡一遍（把较大的数归位），再从后往前冒泡一遍（把较小的数归位），此时操作数量\(2(n-1)\)恰好不会引发交换

实现的时候由于上限比较宽松可以直接重复上述操作

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    int n; std::cin >> n;
    std::string s("");

#define IF_WIN std::cin >> s; if(s == "WIN") exit(0)

    for(;;) {
        for(int i = 1; i < n; ++i) {
            std::cout << i << ' ' << i + 1 << std::endl;
            IF_WIN;
        }
        for(int i = n; i > 1; --i) {
            std::cout << i - 1 << ' ' << i << std::endl;
            IF_WIN;
        }
    }
    return 0;
}

D. Display

题目转化一下就是给出若干个\(h\)维向量，求个数最少的向量使得它们的和中的某一维超过\(s\)

枚举最后超出的是哪一维，很显然只选择这一维最大的那个向量是最优的

#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,w,h,s,mx[N],ans_len=1e9; char ch[N],ans_ch;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	RI i,j,k; for (cin>>n>>w>>h>>s,i=1;i<=n;++i)
	{
		string cur; cin>>cur;
		for (j=1;j<=h;++j)
		{
			string row; cin>>row;
			row="."+row+"."; int cnt=0;
			for (k=1;k<row.size();++k)
			if (row[k]!=row[k-1]) ++cnt;
			if (cnt>mx[j]) mx[j]=cnt,ch[j]=cur[0];
		}
	}
	for (i=1;i<=h;++i)
	{
		if (mx[i]==0) continue;
		int tmp=(s+mx[i]-1)/mx[i];
		if (tmp<ans_len) ans_len=tmp,ans_ch=ch[i];
	}
	for (i=1;i<=ans_len;++i) cout<<ans_ch;
	return 0;
}

E. Easy Compare-and-Set

首先发现可以先处理\(w_i=1\)的操作，\(w_i=0\)的操作最后讨论一下即可

离散化后把数值看作点，一个\(w_i=1\)操作看作一条有向边，则题目等价于找一个从\(c\)出发的路径经过所有边恰好一次

注意到这等价于图存在欧拉回路/存在以\(c\)为起点的欧拉通路

有向图存在欧拉回路的条件：所有点出度入度相同；有向图存在欧拉通路的条件：有且仅有一个点出度比入度大\(1\)（起点），有且仅有一个点入度比出度大\(1\)（终点）

另外还需要判断图是否连通，具体实现看代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,c,a[N],b[N],w[N],in[N],out[N],fa[N],vis[N];
vector <pi> v[N]; vector <int> path;
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void addedge(CI x,CI y,CI z)
{
	v[x].push_back(pi(y,z)); ++out[x]; ++in[y];
}
inline void DFS(CI now)
{
	while (!v[now].empty())
	{
		auto [to,id]=v[now].back(); v[now].pop_back();
		if (vis[id]) continue; DFS(to); vis[id]=1; path.push_back(id);
	}
}
int main()
{
	RI i; scanf("%d%d",&n,&c); vector <int> rst;
	for (rst.push_back(c),i=1;i<=n;++i)
	scanf("%d%d%d",&a[i],&b[i],&w[i]),rst.push_back(a[i]),rst.push_back(b[i]);
	sort(rst.begin(),rst.end()); rst.erase(unique(rst.begin(),rst.end()),rst.end());
	auto find=[&](CI x)
	{
		return lower_bound(rst.begin(),rst.end(),x)-rst.begin()+1;
	};
	for (c=find(c),i=1;i<=n;++i) a[i]=find(a[i]),b[i]=find(b[i]);
	int m=rst.size(); for (i=1;i<=m;++i) fa[i]=i;
	vector <int> key; for (i=1;i<=n;++i)
	if (w[i]==1) addedge(a[i],b[i],i),fa[getfa(a[i])]=getfa(b[i]),key.push_back(a[i]),key.push_back(b[i]);
	for (i=1;i<key.size();++i) if (getfa(key[0])!=getfa(key[i])) return puts("No"),0;
	int cnt_s=0,cnt_t=0,s,t;
	for (i=1;i<=m;++i)
	{
		if (abs(in[i]-out[i])>1) return puts("No"),0;
		if (in[i]+1==out[i]) ++cnt_s,s=i;
		if (out[i]+1==in[i]) ++cnt_t,t=i;
	}
	if ((cnt_s==0&&cnt_t==0)||(cnt_s==1&&cnt_t==1&&s==c))
	{
		DFS(c); reverse(path.begin(),path.end());
		for (i=1;i<=n;++i) if (w[i]==1&&!vis[i]) return puts("No"),0;
		int ots=0; for (i=1;i<=n;++i) if (w[i]==1&&b[i]!=c) ots=i;
		vector <int> ans; for (i=1;i<=n;++i) if (w[i]==0&&a[i]!=c) ans.push_back(i),vis[i]=1;
		for (auto cur:path)
		{
			ans.push_back(cur);
			if (cur==ots)
			{
				for (i=1;i<=n;++i) if (!vis[i]) ans.push_back(i),vis[i]=1;
			}
		}
		for (i=1;i<=n;++i) if (!vis[i]) return puts("No"),0;
		puts("Yes"); for (auto x:ans) printf("%d ",x);
	} else puts("No");
	return 0;
}

F. Futures Market Trends

数据范围不大，可以直接确定左端点后扩展右端点，考虑每次快速维护\(A,D\)的变化

比赛的时候徐神写了分别维护二次项的和、一次项的和的做法，后面发现其实直接用方差等于平方的期望减去期望的平方来做更简单

#include <bits/stdc++.h>

using llsi = long long signed int;

llsi d, c[3003], x[3003];
long double P;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> d >> P;
    for(int i = 1; i <= d; ++i) std::cin >> c[i]; c[0] = 0;
    for(int i = 1; i <= d; ++i) x[i] = c[i] - c[i - 1];
    int pos = 0, neg = 0;
    for(int i = 1; i <= d; ++i) {
        llsi sx = 0, sx2 = 0;
        for(int j = i + 1; j <= d; ++j) {
            sx2 += x[j] * x[j];
            sx  += x[j];
            int n = j - i;
            if(n >= 2 && (long double)sx * sx >= P * P * (long double)(n * sx2 - sx * sx)) {
                if(sx > 0) pos += 1;
                if(sx < 0) neg += 1;
            }
        }
    }

    std::cout << pos << ' ' << neg << std::endl;

    return 0;
}

G. Grammar Path

题目看着都是如此的毒瘤

H. Heroes of Coin Flipping

祁神想了挺久的这个题，搞了个虚树+大讨论的做法，后面也没写过不知道正确性（主要题解也看不懂是俄语的）

I. Integer Square

签到题，直接枚举即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int s;
int main()
{
	scanf("%d",&s);
	for (RI i=0;i*i<=s;++i) for (RI j=0;j*j<=s;++j)
	if (i*i+j*j==s)
	{
		printf("%d %d\n",0,0);
		printf("%d %d\n",i,j);
		printf("%d %d\n",-j,i);
		printf("%d %d\n",i-j,i+j);
		return 0;
	}
	return puts("Impossible"),0;
}

J. Joint Password Storage

题目都哈人的一笔，鉴定为不可做题

K. Keys and Locks Boolean Logic

数电题目来了，祁神后面提出一种通用做法，先找出最简的或与式，然后手玩一下可以找到怎么构造与逻辑和或逻辑

但感觉不知道能不能在限制内做出来，同时这题的输入输出感觉都要写大模拟，做不了一点

L. Lost Permutation

ORZ群论大师徐神大力秒了此题，不然我们队后面两个半小时就只能玩手机了

考虑令\(f=[1,2,3,\cdots,n]\)，最后得到的结果一定也是\([1,2,3\cdots,n]\)

那么如果我们交换\(f\)中的两项会得到什么呢（假设交换了\(x,y\)），手玩一下会发现最后会得到一个只有两个数没有还原的排列

并且我们惊喜地发现这个序列中没有还原的两个数恰好是\(\pi(x),\pi(y)\)上的数

那么我们很容易想到一个naive的做法，例如固定\(x\)，问出\((x,y_1),(x,y_2)\)，找到它们返回的没有还原的数中的众数就是\(\pi(x)\)的值

但现在的问题是我们只能问两次，上面的做法看似完全不可行

不过徐神发现可以只问\([2,1,3,4,\cdots,n-1,n]\)（只交换前两个数）和\([1,3,4,5,\cdots,n,2]\)（固定第一个数，其余的数循环移位）这两个排列，用它们构造出所有的询问情况

（因为询问的信息可以相乘再利用，比如询问\(f_1,f_2\)得到的结果为\(g_1,g_2\)，那么询问\(f_1\cdot f_2\)的结果就是\(g_1\cdot g_2\)）

总复杂度\(O(n^2)\)，实现起来需要一定技巧和细节

      
#include <bits/stdc++.h>

struct pm: public std::vector<int> {
    inline pm(size_t n): vector(n) {}
    friend pm operator*(const pm &a, const pm &b) {
        pm c(a.size());
        for(int i = 0; i < a.size(); ++i) c[i] = b[a[i]];
        return c;
    }
};

void work() {
    int n; std::cin >> n;
    std::cout << "? 2 1";
    for(int i = 3; i <= n; ++i) std::cout << ' ' << i;
    std::cout << std::endl;
    pm a(n); for(auto &a: a) std::cin >> a, --a;
    std::cout << "? 1";
    for(int i = 3; i <= n; ++i) std::cout << ' ' << i;
    std::cout << " 2" << std::endl;
    pm b(n), bi(n), bs(n), be(n); for(auto &b: b) std::cin >> b, --b;
    for(int i = 0; i < n; ++i) bi[b[i]] = i;
    for(int i = 0; i < n; ++i) be[i] = bs[i] = i;
    for(int i = 0; i < n - 1; ++i) be = b * be;
    std::vector<std::vector<int>> sns(n, std::vector<int>());
    for(int i = 1; i < n; ++i) {
        int pi = i;
        pm ars(n); for(int j = 0; j < n; ++j) ars[j] = j;
        ars = be * a * bs * ars;
        // std::cerr << "debug ars:";
        // for(int j = 0; j < n; ++j) std::cerr << ars[j] + 1 << char(j == n - 1 ? 10 : 32);
        for(int j = 0; j < n; ++j) if(ars[j] != j) {
            sns[0].push_back(j);
            sns[i].push_back(j);
        }
        bs = b  * bs;
        be = bi * be;
    }
    std::sort(sns[0].begin(), sns[0].end());
    int a0, a0c = 0; {
        int l = 0, r = 0;
        while(l < sns[0].size()) {
            while(r < sns[0].size() && sns[0][r] == sns[0][l]) r += 1;
            if(r - l > a0c) {
                a0 = sns[0][l];
                a0c = r - l;
            }
            l = r;
        }
    }
    std::cout << "! " << a0 + 1;
    for(int i = 1; i < n; ++i) for(auto sns: sns[i])
        if(sns != a0) std::cout << ' ' << sns + 1;
    std::cout << std::endl;
    return ;
}

int main(void) {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t;
    while(t--) work();
    return 0;
}

M. Mind the Gap

祁神开场写的，我题目都没看

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

const int N = 1e5+5;
int n, A[N];
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	A[0]=0;
	for (int i=1; i<=n; ++i) cin >> A[i];
	sort(A+1, A+n+1);
	int L=1, R=(int)1e9;
	int ans=0;
	while (L<R){
		int M = L+(R-L)/2;
		bool f1=false, f2=false;
		for (int i=0; i<n; ++i) if (A[i+1]-A[i]>M) f1=true;
		for (int i=0; i<n-1; ++i) if (A[i+2]-A[i]<=M) f2=true;
		if (f1 && f2) break;
		else if (f1) L=M+1;
		else if (f2) R=M;
		else{ans=M; break;}
	}
	cout << ans << '\n';
	return 0;	
}

N. Nunchucks Shop

我只看了个题意就被祁神秒了

枚举在一边的珠子的个数，根据奇偶性讨论一下中心对称的方案数

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

const int N = 55;
int C[N][N];
int n, k;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	C[1][0]=C[1][1]=C[0][0]=1;
	for (int i=2; i<N; ++i){
		C[i][0]=C[i][i]=1;
		for (int j=1; j<i; ++j){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
//			printf("C(%lld %lld)=%lld\n", i, j, C[i][j]);
		}
	}
	cin >> n >> k;
	int ans=0;
	for (int x=0; x<=n; ++x){
		if (k-x<0 || k-x>n) continue;
		int res=0;
		if (n%2==0 && x%2==1) res += C[n][x]/2;
		else res += (C[n][x]-C[n/2][x/2])/2+C[n/2][x/2];
		if (k%2==0 && x==k/2) res*=2;
		ans += res;
//		printf("x=%lld res=%lld\n", x, res);
	}
	cout << ans << '\n';
	
	return 0;	
}

Postscript

这场题感觉没啥区分度，前面的题很简单后面的题又极难，而且感觉考的都比较诡异，和国内的风格不太像说是

标签：case,std,North,Northern,puts,Contest,int,ITMO,break
From： https://www.cnblogs.com/cjjsb/p/17985718

相关文章

  • Xmas Contest 2021 D Determinant?
    由Amitsur-Levitzki定理，当\(n\ge2k\)时，答案为\(0\)矩阵。否则我们考虑答案矩阵的某一位\(b_{i,j}\)，其必然由某些路径\(i=p_0\top_1\to\\cdots\top_n=j\)贡献而来，一条路径的贡献为\(\text{sgn}(\sigma)\cdot\prod\limits_{i=1}^nA_{\sigma(i),p_{i-1},p_{i}}\)。......
  • contest/1922 D Berserk Monster
    来来来，看看英语不好的我最开始理解的题目是怎么样的：（1）有一堆怪物在打架，每一次从左到右，一只怪物向离自己最近的怪物攻击一次，每一次怪物都攻击一次后会死掉多少只怪物。怎么做......（2）仔细阅读以后发现可能是所有怪物同时发动攻击。变简单了。（3）再阅读，发现所有怪物被攻击以后，受到的......
  • AtCoder Regular Contest 170 A-C
    A-YetAnotherABProblem贪心。定义下标\(i\)满足\(S[i]=B,T[i]=A\)为\(BA\)型，\(S[i]=B,T[i]=A\)为\(AB\)型，\(AA\)型、\(BB\)型同理。对所有\(BA\)型的下标\(i\)去匹配其右侧的第一个\(AB\)型的下标\(j\)，匹配成功则对下标\(i\)和\(j\)进行操作，若无法匹配，则对剩余的\(BA\)型......
  • AtCoder Regular Contest 170 D Triangle Card Game
    洛谷传送门AtCoder传送门赛后调了40min，哈哈。首先先把\(a,b\)排序。考虑先枚举Alice选的数\(a_i\)，然后若\(\forallj,\existsk\nei,(a_i,b_j,a_k)\)能组成三角形，Alice就赢了。考虑简化条件。\((x,y,z)\)能形成三角形的充要条件是\(z\in(|x-y|,x+......
  • Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337）
    ToyotaProgrammingContest2024#1（AtCoderBeginnerContest337）A-Scoreboard代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;void......
  • AtCoder Beginner Contest 337
    基本情况ABC秒了，D数组在空间复杂度上面第一次疯狂吃亏，吃了两次罚时过。赛后看官方题解，发现C做法薄纱我。C-LiningUp2https://atcoder.jp/contests/abc337/tasks/abc337_c这题一眼链表，我用双向链表实现，代码石山。官方题解就题论题，更本质。其实这题并没必要开双向链......
  • Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337）
    ToyotaProgrammingContest2024#1（AtCoderBeginnerContest337）比赛链接A-Scoreboard思路简单的模拟，统计一下总分数就可以了Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn; intans1=0; intans2=0; cin>>n; for......
  • AtCoder Beginner Contest 337
    AtCoderBeginnerContest337赛后总结A题不多说，纯水。B题对题目要求没有理解太透（不知道是英语问题，还是它样例给的不够全，没太能理解最后的那个判断结果）卡c题上了c题感觉其实是个比较有意思的题，但是只要理解了题目就知道本质是一个求数组对应的下标，再以数组的下标所对应的数组......
  • AtCoder Beginner Contest 336
    AtCoderBeginnerContest336A-LongLoong代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;voidsolve(){intn;cin>&g......
  • AtCoder Beginner Contest 337
    AtCoderBeginnerContest337做题顺序有点奇怪。先做的C。套路题。令\(to_i\)表示\(i\)的下一个点是什么。2min过了。再做的B。智障题。令\(now\)表示现在在哪个字符（A或B或C），然后挨个字符跳。结果真成智障了，第一发没判断A跳到C的情况，罚时+1。又做的A。入......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99