首页 > 其他分享 >2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)

2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)

时间:2024-01-13 19:55:45浏览次数:28  
标签:Northwestern return Pt pt Contest int 2021 && include

Preface

和昨天刚好相反,前期极度崩盘2h2题而且一堆银铜牌题不会

但好在后面稳扎稳打慢慢追回来了一点,最后超高罚时8题收场

这场一边打一边看ECF的实况,最后看到同校的Wifi暴打全场,实在是ORZ


A. Access Denied

签到,首先暴力问出长度然后从前往后一位一位确定即可

注意实现的时候不需要特意去算返回的秒数的含义,只要找一个和其它返回结果不同的即可

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#define RI register int
#define CI const int&
using namespace std;
inline int ask(string s)
{
    cout<<s<<endl;
    string t; getline(cin,t);
    if (t[7]=='G') exit(0);
    int ret=0; for (RI i=15;;++i)
    if (t[i]>='0'&&t[i]<='9') ret=ret*10+t[i]-'0'; else break;
    return ret;
}
int main()
{
    for (;;)
    {
        RI i,j,k; int res[100],len;
        for (i=1;i<=20;++i)
        {
            string s(i,'a'); res[i]=ask(s);
        }
        for (i=1;i<=20;++i)
        {
            bool flag=1; for (j=1;j<=20;++j)
            if (i!=j&&res[i]==res[j]) { flag=0; break; }
            if (flag) { len=i; break; }
        }
        string ans="";
        for (i=1;i<=len;++i)
        {
            for (j=1;j<=62;++j)
            {
                string s=ans;
                if (j>=1&&j<=26) s+='a'+j-1;
                if (j>=27&&j<=52) s+='A'+j-27;
                if (j>=53&&j<=62) s+='0'+j-53;
                for (k=1;k<=len-i;++k) s+='a';
                res[j]=ask(s);
            }
            for (j=1;j<=62;++j)
            {
                bool flag=1; for (k=1;k<=62;++k)
                if (j!=k&&res[j]==res[k]) { flag=0; break; }
                if (flag)
                {
                    if (j>=1&&j<=26) ans+='a'+j-1;
                    if (j>=27&&j<=52) ans+='A'+j-27;
                    if (j>=53&&j<=62) ans+='0'+j-53;
                    break;
                }
            }
        }
        ask(ans);
    }
    return 0;
}

B. Boredom Buster

另一个好难的交互,题都没看


C. Cutting Edge

最近每次我正序开题都能开到防AK题,继承徐神特性了属于是


D. Dyson Circle

徐神比赛时提出的做法思路比较自然,把一个关键格子的四个角的坐标都标出来,然后对所有标出来的点跑一个凸包

最后将凸包上的相邻点连接起来几个,贡献就是两点间横纵坐标之差取\(\max\)

但写完遇到第三个样例发现需要修正,当所有点在同一条对角线上时答案需要加\(1\),这个手玩下第三个样例很好理解

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

const int N = 2e5+5;
int n;
int stk[N*4], top=-1;
struct Pt{
	int x, y;
	int crs(Pt b){return x*b.y-y*b.x;}
	Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
	bool operator<(Pt b)const{return x!=b.x ? x<b.x : y<b.y;}
}pt[N*4];

int makeCH(){
	int sz = n*4;
	sort(pt, pt+sz);
	stk[++top] = 0;
	for (int i=1; i<sz; ++i){
		while (top>0 && (pt[stk[top]]-pt[stk[top-1]]).crs(pt[i]-pt[stk[top-1]])<=0) --top;
		stk[++top] = i;
	}
	int mx = top;
	for (int i=sz-2; i>=0; --i){
		while (top>mx && (pt[stk[top]]-pt[stk[top-1]]).crs(pt[i]-pt[stk[top-1]])<=0) --top;
		stk[++top] = i;
	}
	return top;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	if (n==1){
		cout << 4 << '\n';
		return 0;
	}
	int t1=0, t2=0;
	bool ok1=true, ok2=true;;
	for (int i=0; i<n; ++i){
		int x, y; cin >> x >> y;
		if (0==i) t1=x+y, t2=x-y;
		else{
			if (t1!=x+y) ok1=false;	
			if (t2!=x-y) ok2=false;	
		}
		pt[i*4+0].x = x, pt[i*4+0].y = y;
		pt[i*4+1].x = x+1, pt[i*4+1].y = y;
		pt[i*4+2].x = x, pt[i*4+2].y = y+1;
		pt[i*4+3].x = x+1, pt[i*4+3].y = y+1;
	}
	
	int sz = makeCH();
//	for (int i=0; i<sz; ++i){
//		printf("(%d %d)\n", pt[stk[i]].x, pt[stk[i]].y);
//	}	
	int ans=0;
	for (int i=0; i<sz; ++i){
		ans += max(abs(pt[stk[i]].x-pt[stk[(i+1)%sz]].x), abs(pt[stk[i]].y-pt[stk[(i+1)%sz]].y));	
	}
	if (ok1 || ok2){
		cout << ans + 1 << '\n';
	}else cout << ans << '\n';
	return 0;	
}

PS:赛后看了题解做法发现原来很trivial,最后的答案一定是个大的斜矩形,不过特判还是避免不了的


E. Exchange Students

挺有意思的一个题,最后20min才有时间看,之后有时间仔细想想


F. Flatland Olympics

徐神秒出思路最后祁神顶住压力上去快速过了这个题,那我在干嘛(原来是在边上打雀魂)

首先特判掉点在跑道延长线上的情况,以及另外一些奇奇怪怪的边界问题

然后可以沿着线段所在的直线把平面分成两块,显然每一块的求解是独立的

对于每一块,不妨从跑道的某个端点为起点对所有点做一个极角排序,然后把这个排名记为这个点的第一位特征

以此类推对于跑道的另一个端点也搞出一个排名,然后画画图会发现题目要求的等价于一个二维偏序问题

直接排序后用树状数组维护下即可,总复杂度\(O(n\log n)\)

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

const int N = 2e5+5;
int n;
struct Pt{
	int x, y;
	int crs(Pt b){return x*b.y-y*b.x;}
	int dot(Pt b){return x*b.x+y*b.y;}
	Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
}pt[N];
int cross(Pt p, Pt a, Pt b){return (a-p).crs(b-p);}

struct Fenwick{
	int cnt[N];
	int lb(int x){return x&(-x);}
	void upd(int pos, int val){for (int i=pos; i<=n; i+=lb(i)) cnt[i]+=val;}
	int qry(int pos){int res=0; for (int i=pos; i>0; i-=lb(i)) res+=cnt[i]; return res;}
	void init(){for (int i=1; i<=n; ++i) cnt[i]=0;}
}fen;

vector<int> up, dn, line1, line2;
int px[N], py[N], idx=0, idy=0;

int solve1(Pt s0, Pt e0, vector<int> &vec){
	if (vec.empty()) return 0;
	memset(px, 0, (n+1)*sizeof(int));
	memset(py, 0, (n+1)*sizeof(int));
	sort(vec.begin(), vec.end(), [&](int a, int b){
		return cross(s0, pt[a], pt[b])>=0;
	});
	idx=idy=0;
	px[vec[0]]=++idx;
	for (int i=1; i<(int)vec.size(); ++i){
		if (cross(s0, pt[vec[i]], pt[vec[i-1]])!=0) ++idx;
		px[vec[i]] = idx;
	}
	
	sort(vec.begin(), vec.end(), [&](int a, int b){
		return cross(e0, pt[a], pt[b])<=0;
	});
	py[vec[0]]=++idy;
//		printf("i=%d (%lld %lld)\n", 0, pt[vec[0]].x, pt[vec[0]].y);
	for (int i=1; i<(int)vec.size(); ++i){
//		printf("i=%d (%lld %lld)\n", i, pt[vec[i]].x, pt[vec[i]].y);
		if (cross(e0, pt[vec[i]], pt[vec[i-1]])!=0) ++idy;
		py[vec[i]] = idy;
	}
	
	sort(vec.begin(), vec.end(), [&](int a, int b){
		return px[a]!=px[b] ? px[a]<px[b] : py[a]<py[b]; 	
	});
//	printf("vec:"); for (int x : vec) printf("%lld ", x); puts("");
//	printf("px:"); for (int i=1; i<=n; ++i) printf("%lld ", px[i]); puts("");
//	printf("py:"); for (int i=1; i<=n; ++i) printf("%lld ", py[i]); puts("");
	fen.init();
	int res=0;
	for (int a : vec){
//		printf("a=%d px=%d py=%d\n", a, px[a], py[a]);
		res += fen.qry(py[a]);
		fen.upd(py[a], 1);
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	Pt s, e;
	cin >> s.x >> s.y >> e.x >> e.y;
	cin >> n;
	for (int i=1; i<=n; ++i){
		cin >> pt[i].x >> pt[i].y;
		int crs = cross(s, e, pt[i]);
		if (crs>0) up.push_back(i);
		else if (crs<0) dn.push_back(i);
		else{
			if ((e-s).dot(pt[i]-s)>0) line1.push_back(i);
			else line2.push_back(i);
		}
	}
	int ans=0;
	ans += solve1(s, e, up);
	ans += solve1(e, s, dn);
//	printf("ans=%lld\n", ans);
//	printf("l1=%lld l2.size=%lld\n", line1.size(), line2.size());
	ans += (int)(line1.size()-1)*line1.size()/2;
	ans += (int)(line2.size()-1)*line2.size()/2;
	cout << ans << '\n';
	
	return 0;	
}

G. Glossary Arrangement

祁神和徐神写的,我题目都没看,好像是二分行数后套个DP检验一下

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

const int N = 5e3+5;
int n, w;
string str[N];
int f[N], g[N], path[N], width[N], wd[N];
int mp[N][N];

int check(int x){
	memset(f, 0, sizeof(n+1));
	f[0]=-1, g[0]=0, path[0]=0;
	for (int i=1; i<=n; ++i){
		int len=str[i].length();
		f[i] = 1e9, g[i]=i;
		for (int j=i-1; j>=0 && i-j<=x; --j){
//			printf("i=%d j=%d len=%d\n", i, j, len);
			if (f[j]+len+1 < f[i]){
				f[i] = min(f[i], f[j]+len+1);
				g[i] = g[j]+1;
				path[i] = j;
				wd[i] = len;
			}
			len = max(len, (int)str[j].length());
//			if (str[j].length() > str[i].length()) break;
		}
	}
	
	if (f[n]>w) return false;
	else return true;
}

void print(int r, int c){
	if (mp[r][c]==0) for (int i=0; i<=width[c]; ++i) cout << ' ';
	else{
		cout << str[mp[r][c]];
		for (int i=str[mp[r][c]].length(); i<=width[c]; ++i) cout << ' ';
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> w;
	for (int i=1; i<=n; ++i) cin >> str[i];
	int L=1, R=n;
	while (L<R){
		int M = L+(R-L)/2;
//		printf("L=%d R=%d M=%d\n", L, R, M);
		int mx=-1;
		if (check(M)) R=M;
		else L=M+1;
//		printf("L=%d R=%d mx=%d\n", L, R, mx);
//		printf("f:"); for (int i=1; i<=n; ++i) printf("%d ", f[i]); puts("");
//		printf("g:"); for (int i=1; i<=n; ++i) printf("%d ", g[i]); puts("");
//		printf("path:"); for (int i=1; i<=n; ++i) printf("%d ", path[i]); puts("");
	}
	check(L);
//	printf("R=%d, C=%d\n", L, g[n]);
	
	int cur=n, lst=path[n], r=cur-lst, c=g[n];
//	printf("r=%d, c=%d cur=%d\n", r, c, cur);
	width[c] = wd[n];
	while (cur>0){
		if (cur == lst){
//			printf("cur=%d lst=%d\n", cur, lst);
			lst = path[cur];
			--c;
			r=cur-lst;
			width[c] = wd[cur];
		}
		mp[r][c] = cur;
		--r;
		--cur;
	}
//	for (int i=0; i<=L; ++i){
//		for (int j=0; j<=g[n]; ++j){
//			printf("%d ", mp[i][j]);	
//		}puts("");
//	}
	cout << L << ' ' << g[n] << '\n';
	for (int i=1; i<=g[n]; ++i) cout<< width[i] << (i==g[n] ? '\n' : ' ');
	for (int i=1; i<=L; ++i){
		for (int j=1; j<=g[n]; ++j){
			print(i, j);	
		}cout << '\n';
	}
	
	return 0;	
}

H. Heating Up

徐神前面提了个笛卡尔树的做法,后面我感觉如果真是这样的话过的人肯定没这么多,后面搞了个相对简单的做法直接艹了过去

首先答案具有二分性,考虑如何check,首先要注意到我们将原序列倍长后处理和在环上处理是等价的

然后考虑如果选择了某个起点,最后扩展出的区间是\([l,r]\),那么显然以\([l,r]\)中的任何一个点作为起点扩展出的区间都是\([l,r]\),就无需再考虑了

但如果直接上按顺序扫描一遍来做的话又会有一个问题就是向前扩展时带来的复杂度消耗很大

因此我们不妨搞个双向链表,然后扩展的时候把点合并一下就能保证复杂度了,具体实现可以看代码

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,s[N],a[N],b[N],L[N],R[N];
inline bool check(CI st)
{
    RI i; for (i=1;i<=n;++i) a[i]=a[i+n]=b[i]=b[i+n]=s[i];
    for (i=1;i<=2*n;++i) L[i]=i-1,R[i]=i+1;
    R[0]=1; L[2*n+1]=2*n; a[0]=a[2*n+1]=6e18;
    for (i=1;i<=2*n;i=R[i])
    {
        if (a[i]>st) continue;
        int tmp=st+b[i];
        auto remove=[&](CI x)
        {
            int pre=L[x],nxt=R[x];
            R[pre]=nxt; L[nxt]=pre;
        };
        for (;;)
        {
            if (a[L[i]]>tmp&&a[R[i]]>tmp) break;
            if (a[L[i]]<=tmp)
            {
                a[i]=min(a[i],a[L[i]]);
                b[i]+=b[L[i]]; tmp+=b[L[i]]; remove(L[i]);
            }
            if (a[R[i]]<=tmp)
            {
                a[i]=min(a[i],a[R[i]]);
                b[i]+=b[R[i]]; tmp+=b[R[i]]; remove(R[i]);
            }
        }
    }
    return R[R[0]]==2*n+1;
}
signed main()
{
    RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&s[i]);
    int l=0,r=1e13,mid,ret; while (l<=r)
    if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
    return printf("%lld",ret),0;
}

I. IXth Problem

题目都没看,弃疗


J. Jet Set

妈的因为没判经度相同的情况一直WA给我写红温了,过了这题后全队的节奏就对起来了

首先注意到纬度是没有用的,而每次相邻的两点大圆航线总是会走经度变化较少的一边

而如果出现两个点经度差恰好为\(180\degree\),那么它们的大圆航线一定过极点

因此特判上面那种情况后拿个数组模拟一下即可,至于处理\(.5\)经度的话把所有点下标乘\(2\)最后再除即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
const int N=1005,S=360;
int n,phi,d[N],vis[N];
int main()
{
    RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",&phi,&d[i]);
    for (d[n+1]=d[1],j=1;j<=n;++j)
    {
        int s=d[j]*2,t=d[j+1]*2;
        if (abs(s-t)==360) return puts("yes"),0;
        if (s==t) { vis[s+S]=1; continue; }
        if (t>s&&t-s<360)
        {
            for (i=s;i<=t;++i) vis[i+S]=1;
        } else
        if (t<s&&(360-s)+(t+360)<360)
        {
            for (i=s;i<360;++i) vis[i+S]=1;
            for (i=-360;i<=t;++i) vis[i+S]=1;
        } else
        if (t<s&&s-t<360)
        {
            for (i=t;i<=s;++i) vis[i+S]=1;
        } else
        {
            for (i=t;i<360;++i) vis[i+S]=1;
            for (i=-360;i<=s;++i) vis[i+S]=1;
        }
    }
    int pos=360; for (i=-360;i<360;++i) if (!vis[i+S]) pos=i;
    if (pos==360) return puts("yes"),0;
    int x=pos/2,y=pos%2?5:0;
    if (pos==-1) puts("no -0.5"); else printf("no %d.%d",x,y);
    return 0;
}

K. Knitpicking

签到,直接枚举最后配对的是那种袜子

对于其它的袜子,要么在左右脚中取较大的一个,要么取一个任意脚的

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

int n;
struct Sock{
	int a, l, r;	
};
map<string, Sock> mp;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; ++i){
		string s1, s2;
		int cnt;
		cin >> s1 >> s2 >> cnt;
		if (s2[0]=='a'){
			mp[s1].a=cnt;	
		}else if (s2[0]=='l'){
			mp[s1].l=cnt;	
		}else if (s2[0]=='r'){
			mp[s1].r=cnt;	
		}
	}
		bool ok=false;
		int ans=0;
//		for (auto [a, l, r] : mp){
		for (auto it = mp.begin(); it!=mp.end(); ++it){
			auto [a, l, r] = it->second;
//			a = it->a, l=it->l, r=it->r
			if (a>=2 || (l>0&&r>0)) ok=true;
			ans += max(max(l, r), (a>0 ? 1 : 0));
		}
		if (!ok) cout << "impossible\n";
		else cout << ans+1 << '\n';
	
	return 0;	
}

L. Lucky Shirt

这题前面徐神提了一堆诸如模拟若干次的做法,但后面我灵光一闪发现一个关键点就迎刃而解了

首先这题最关键的就是要注意到这题的操作是“无前效性”的,比如我们找到最终操作的最大长度\(x\),则所有操作的影响可以看作只进行了一次长度为\(x\)的打乱操作

因此这题的思路就很简单了,先考虑求\(f(x)\)表示进行的\(k\)次操作中最大的打乱长度为\(x\)的概率

这个可以用经典容斥,设\(g(x)\)表示进行的\(k\)次操作中最大的打乱长度为\(\ge x\)的概率,则\(g(x)=1-(\frac{x-1}{n})^k\),同时\(f(x)=g(x)-g(x+1)\)

然后知道\(f(x)\)后我们简单讨论下即可:

  • \(x<i\),则这次操作不会对\(i\)位置产生影响,贡献为\(f(x)\times i\)
  • \(x\ge i\),则这次操作会把\(i\)等概率地打乱到\([1,x]\)中,贡献为\(f(x)\times \frac{1+x}{2}\)
#include <bits/stdc++.h>

using real = long double;

real ksm(real a, int b) {
    real r = 1.0L;
    while(b) {
        if(b & 1) r = r * a;
        a = a * a;
        b >>= 1;
    }
    return r;
}

int n, i, k;
real g(int x) {
    return 1 - ksm(real(x - 1) / n, k);
}

real f(int x) {
    return g(x) - g(x + 1);
}

int main() {
    std::cin >> n >> i >> k;
    std::cout << std::fixed << std::setprecision(20);
    real ans = 0;
    for(int j = 1; j <  i; ++j) ans += i * f(j);
    for(int j = i; j <= n; ++j) ans += real(j + 1) * f(j) * 0.5L;
    std::cout << ans << char(10); 
    return 0;
}

Postscript

明天找场简单点的提提信心,今天前面差点红温爆炸了说是

标签:Northwestern,return,Pt,pt,Contest,int,2021,&&,include
From: https://www.cnblogs.com/cjjsb/p/17962831

相关文章

  • AtCoder Beginner Contest 335 G Discrete Logarithm Problems
    洛谷传送门AtCoder传送门考虑若我们对于每个\(a_i\)求出来了使得\(g^{b_i}\equiva_i\pmodP\)的\(b_i\)(其中\(g\)为\(P\)的原根),那么\(a_i^k\equiva_j\pmodP\)等价于\(kb_i\equivb_j\pmod{P-1}\),有解的充要条件是\(\gcd(b_i,P-1)\midb_j\)。显然......
  • AtCoder Beginner Contest 335 (Sponsored by Mynavi)
    AtCoderBeginnerContest335(SponsoredbyMynavi)A-2023代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondvoidsolve(){strings;cin>>s;......
  • AtCoder Beginner Contest 335 总结
    ABC335总结A.202<s>3</s>翻译给你一个由小写英文字母和数字组成的字符串\(S\)。\(S\)保证以2023结尾。将\(S\)的最后一个字符改为4,并打印修改后的字符串。分析两种做法:直接把最后一个字符改为4,然后输出。输出前\(n\)个字符后输出4。code#include<bits/stdc......
  • AT_zone2021 部分
    前言教练出了个集训赛,就是AT_zone2021vp,赛时没切E,赛后也不想做E,所以不写。ZONe_a用substr拆出来,然后检查是不是ZONe。Code#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings; cin>>s; intans=0; for(inti=0;i<s.size()-4;i++)if(s.substr(......
  • Windows 10 on ARM, version 21H2 (released Nov 2021) ARM64 简体中文版、英文版(企业
    作者主页:sysin.orgWindows10,version21H2(releasedNov2021)ARM64ChineseSimplifiedWindows10,version21H2(releasedNov2021)ARM64English基于ARM的Windows10起初,Windows10(与Windows10移动版不同)只能在采用x86和x64处理器的电脑上运行。现在,Windows10......
  • Office 2021 简体中文 正式版 零售版 32位和64位 官方镜像下载合集
    Office2021零售版1、OfficeProfessionalPlus2021,专业增强版:ProPlus2021Retail.img(Previouslyonlyavailableinvlversion,detailsareunknown)2、OfficeProfessional2021,专业版:Professional2021Retail.img(PlusAccessandPublisher(forPConly))3、OfficeHome&B......
  • Windows Server 2022 英文版、简体中文版下载 (updated Oct 2021)
    2021.09.01更新,微软官方确认该版本为正式版:WindowsServer2022nowgenerallyavailable—deliversinnovationinsecurity,hybrid,andcontainers2021.08.19,微软在VLSC和MSDN发上发布了WindowsServer2022镜像下载,虽然并未公开宣布,“releasedAug2021”意味着已经发......
  • Windows Server 2022 英文版、简体中文版下载 (updated Dec 2021)(2022 年 1 月发布)
    WindowsServer2022正式版,2021年12月更新2021.09.01更新,微软官方确认该版本为正式版:WindowsServer2022nowgenerallyavailable—deliversinnovationinsecurity,hybrid,andcontainers2021.08.19,微软在VLSC和MSDN发上发布了WindowsServer2022镜像下载,虽然并......
  • AtCoder Beginner Contest 295
    B-Bombsd难度:⭐题目大意给定一个n*m的网格,其中'.'表示空白,'#'表示障碍物,数字x表示此处有一个炸弹,会将附近曼哈顿距离小于等于x的格子都变成空白;问所有炸弹爆炸后的网格;解题思路数据范围很小,暴力即可;神秘代码#include<bits/stdc++.h>#definei......
  • AtCoder Regular Contest 167 C MST on Line++
    洛谷传送门AtCoder传送门我是傻逼。很平凡的一个计数。但是不会啊。怎么会是呢。考虑Kruskal求解MSTonLine问题。我们可以想到统计边权\(=a_i\)的出现次数。然后又可以容斥转化成统计边权\(\lea_i\)的出现次数,设其为\(f_i\)。考虑求\(f_i\)。就相当于把\(p\)......