Preface

昨天VP的那场没有字符串还没有原形毕露，今天遇到一个后期字符串直接和祁神大眼瞪小眼了

最后一个半小时祁神狂冲F成功写出两个version的假算法，而我已经滚去补之前欠下的题目了

赛后被徐神狠狠拷打了，评价为徐神是我们的红太阳，没有他我们都不能活

A. Orders

签到，按截止时间处理任务即可

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

int t, n, k;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--){
		cin >> n >> k;
		map<int, int> mp;
		for (int i=1; i<=n; ++i){
			int a, b; cin >> a >> b;
//			vec.push_back(Node{a, b});
			mp[a] += b;
		}
		bool ok=true;
		int cur=0;
		for (auto [a, b] : mp){
			cur += b;
			if (cur > a*k){ok=false; break;}	
		}
		cout << ( ok  ? "Yes\n" : "No\n");
	}
	return 0;	
}

B. Building Company

我看完题目人还蒙蔽着，祁神下来看了一眼就会了

考虑任务做了一定不亏，所以就想办法快速维护所有未处理的任务

给每个任务统计一下还有几个维度不满足，用堆来动态更新即可

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

const int N = 1e5+5;
int cnt[N];
struct mes{
	int u, id;
	bool operator<(const mes &b)const{return u>b.u;}	
};
struct Node{
	int cur=0;
	priority_queue<mes> Q;
};
map<int, Node> mp;
vector<pair<int, int> > vec[N];
int que[N], fr=0, ed=-1;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int g; cin >> g;
	for (int i=1; i<=g; ++i){
		int t, u; cin>>t>>u;
		mp[t].cur=u;	
	}
	int n; cin >> n;
	for (int i=1; i<=n; ++i){
		int m; cin >> m;
		for (int j=1; j<=m; ++j){
			int a, b; cin >> a >> b;
			Node &nd=mp[a];
			if (nd.cur < b) nd.Q.push(mes{b, i}), ++cnt[i];
		}
		int k; cin >> k;
		for (int j=1; j<=k; ++j){
			int a, b; cin >> a >> b;
			vec[i].emplace_back(a, b);
		}
	}
	
	for (int i=1; i<=n; ++i) if (0==cnt[i]) que[++ed]=i;	
	while (fr<=ed){
		int x=que[fr++];
		for (auto [t, u] : vec[x]){
			auto &nd = mp[t];
			nd.cur+=u;
			while (!nd.Q.empty() && nd.cur>=nd.Q.top().u){
				--cnt[nd.Q.top().id];
				if (0==cnt[nd.Q.top().id]) que[++ed]=nd.Q.top().id;
				nd.Q.pop();
			}
		}
	}
	
	int ans=0;
	for (int i=1; i<=n; ++i) if (0==cnt[i]) ++ans;
	//for (int i=1; i<=n; ++i) printf("%d ", cnt[i]); puts("");
	cout << ans << '\n';
	return 0;	
}

C. Trie

徐神远程讲出了这题做法的关键，但我是笨比完全策不懂的说

坐等徐神下周补题.png

D. Fast and Fat

思路很好想的一个题，首先最小值最大一眼二分答案，考虑如何检验最小速度为\(v_m\)是否合法

首先可以把人分成两类，一类是\(v_i<v_m\)的，这些人最后一定需要别人来背，可以先都扔进一个multiset里

而另一类人是\(v_j\ge v_m\)的，考虑背人后仍要满足限制，则有\(v_j-(w_i-w_j)\ge v_m\)，即\(w_i\le v_j+w_j-v_m\)

对于这类人我们贪心地在multiset里找一个体重满足限制并且最大的人背上即可，最后看看multiset是否为空

复杂度\(O(n\log^2 n)\)

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

int t, n;
struct Node{
	int v, w;
	bool operator<(const Node &b)const{return v<b.v;}
};

vector<Node> vec;
bool check(int vm){
	multiset<int> st;
	for (auto [v, w] : vec){
		if (v<vm){ st.insert(w); continue;}
		auto it = st.upper_bound(w+v-vm);
		if (it==st.begin()) continue;
		--it;
		st.erase(it);
	}
	return st.empty();
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--){
		cin >> n;
		vec.resize(n);
		for (int i=0; i<n; ++i) cin >> vec[i].v >> vec[i].w;
		sort(vec.begin(), vec.end());
		
		int L=1, R=1e9+5;
		while (L<R){
			int M=L+(R-L)/2+1;
			if (check(M)) L=M;
			else R=M-1;	
		}
		cout << L << '\n';
	}
	return 0;	
}

E. Math Problem

因为特判写伪了两人人大眼看了好久

首先不难发现一定是先做完所有的除法再做乘法，否则如果存在相邻的两个操作一乘一除就相互抵消了，一定是劣的

首先特判掉\(k=1\)的情形，接下来我们发现除法的操作次数是\(\log n\)级别的，可以暴枚

同时考虑枚举接下来的乘法操作次数，这个的上界也是\(\log m\)级别的

判断的具体细则就是维护能得到的数的区间\([L,R]\)，每次\(L'=L\times k,R'=R\times k +(k-1)\)

不难发现区间内的所有数都可以被表示出来，因此只要看\([L,R]\)中是否有\(m\)的倍数即可

单组数据复杂度\(O(\log n\times \log m)\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18+5;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int t, n, k, m, a, b;
	cin >> t;
	while (t--){
		cin >> n >> k >> m >> a >> b;
		if (1==k){
			if (m==1) cout << 0 << '\n';
			else cout << (n%m==0 ? 0 : -1) << '\n';
			continue;	
		}
		
		int ans=INF, res1=0, res2=0;
		while (n>=1){
			__int128 L=n, R=n;
			res2=0;
			while ((L-1)/m == R/m){
				res2+=a; L*=k; R=R*k+k-1;
			}
			ans = min(ans, res1+res2);
			res1+=b; n/=k;
		}
		ans = min(ans, res1);
		cout << ans << '\n';
	}
	return 0;	
}

F. Colorful Segments

这题祁神比赛时候提出的算法正好是出题人题解中讲的假算法，可以说是被完全预判到了

最后这题交给祁神补了，因此我就不写做法了，具体看官方题解吧

G. Matching

签到题，把所有\(a_i-i\)相同的数放在一起，贪心地每次取出最大的两个匹配即可

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


signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int t, n;
	cin >> t;
	while (t--){
		cin >> n;
		map<int, vector<int>> mp;
		for (int i=1; i<=n; ++i){
			int a; cin >> a;
			mp[a-i].push_back(a);
		}
		int ans=0;
		for (auto [v, vec] : mp){
			sort(vec.begin(), vec.end(), greater<int>());	
			for (int i=0; i+1<(int)vec.size(); i+=2){
				int res=vec[i]+vec[i+1];
				if (res<=0) break;
				ans+=res;
			}
		}
		cout << ans << '\n';
	}
	return 0;	
}

H. Be Careful 2

本场放AK题，然而我开场就开到这道题了，看来徐神不在我继承了徐神的被动可还行

I. Three Dice

签到，直接\(6^3\)爆枚即可

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

bool vis[20][20];
signed main(){
	for (int i=1; i<=6; ++i){
		for (int j=1; j<=6; ++j){
			for (int k=1; k<=6; ++k){
				int A=0, B=0;
				if (i==1 || i==4) A+=i; else B+=i;
				if (j==1 || j==4) A+=j; else B+=j;
				if (k==1 || k==4) A+=k; else B+=k;
				vis[A][B]=true;
			}
		}
	}
	int a, b; cin >> a >> b;
	cout << (vis[a][b] ? "Yes\n" : "No\n");
	return 0;	
}

J. Not Another Path Query Problem

很经典的一个题，看一眼就会做了的程度

发现\(V\)是全局固定的，这就启发我们可以先找出一些前缀，满足当选择的边的权值有这个前缀时就一定满足大于等于\(V\)的条件

这个东西很经典，只要将\(V\)的每一个\(0\)的位置尝试替换成\(1\)，然后保留高位的前缀，这样剩下的低位都可以任意取

最后可以发现只需要处理\(O(\log V)\)级别的前缀，那么我们给每个前缀建一张图然后用并查集维护下连通性即可

总复杂度\(O(m\log V\times \alpha(m))\)

#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,m,q,V,x[N],y[N],w[N];
struct DSU
{
	int fa[N];
	inline void init(CI n)
	{
		for (RI i=1;i<=n;++i) fa[i]=i;
	}
	inline int getfa(CI x)
	{
		return fa[x]!=x?fa[x]=getfa(fa[x]):x;
	}
	inline void merge(CI x,CI y)
	{
		fa[getfa(x)]=getfa(y);
	}
	inline bool query(CI x,CI y)
	{
		return getfa(x)==getfa(y);
	}
}D[65];
signed main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	RI i,j; for (cin>>n>>m>>q>>V,i=1;i<=m;++i) cin>>x[i]>>y[i]>>w[i];
	int W=0; vector <int> pre;
	for (i=60;i>=0;--i)
	{
		if ((V>>i)&1LL) { W|=(1LL<<i); continue; }
		pre.push_back(W|(1LL<<i));
	}
	pre.push_back(W); for (i=0;i<pre.size();++i)
	{
		D[i].init(n); for (j=1;j<=m;++j)
		if ((w[j]&pre[i])==pre[i]) D[i].merge(x[j],y[j]);
	}
	//for (auto x:pre) cout<<x<<endl;
	for (i=1;i<=q;++i)
	{
		int u,v; cin>>u>>v; bool flag=0;
		for (j=0;j<pre.size()&&!flag;++j)
		if (D[j].query(u,v)) flag=1;
		cout<<(flag?"Yes":"No")<<'\n';
	}
	return 0;
}

K. Difficult Constructive Problem

连着两题遇到这种字典序问题了，但这个题显然比昨天那个要简单好多

首先注意到一个关键性质，当这个字符串的开头和结尾的字符确定后，最后不管怎么填，相邻的不同pair的奇偶性不会改变

因此可以考虑对后缀做一个DP，令\(f_{i,0/1}=(L,R)\)，表示对于从\(i\)开始的后缀，当\(s_i=0/1\)时，后面能凑出的相邻的不同pair的最小值和最大值

不难发现对于某个区间\([L,R]\)，一定有\(L,R\)的奇偶性相同，并且若\(x\in[L,R]\)且\(x\)和\(L,R\)的奇偶性相同，则\(x\)也可以凑出来

有了这个我们就可以很容易地贪心构造答案了，从前往后每一位优先放\(0\)，用上面的DP数组来保证始终能构造出解即可

具体实现的时候细节比较多，需要注意下，同时对于开头和结尾字符没有确定的情况我们直接暴枚一下即可

总复杂度\(O(n)\)，还有注意特判\(n=1\)的情况

#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
struct ifo
{
	int l,r;
	inline ifo(CI L=INF,CI R=-INF)
	{
		l=L; r=R;
	}
}f[N][2]; int t,n,k; char s[N]; string ans;
inline void solve(void)
{
	RI i; f[n][s[n]-'0']=ifo(0,0); f[n][(s[n]-'0')^1]=ifo();
	for (i=n-1;i>=1;--i)
	{
		f[i][0]=f[i][1]=ifo();
		auto upt=[&](CI x,CI y)
		{
			f[x][y]=ifo(min(f[x+1][y].l,f[x+1][y^1].l+1),max(f[x+1][y].r,f[x+1][y^1].r+1));
		};
		if (s[i]=='?') upt(i,0),upt(i,1); else upt(i,s[i]-'0');
	}
	if (f[1][s[1]-'0'].l%2!=k%2) return;
	if (k<f[1][s[1]-'0'].l||k>f[1][s[1]-'0'].r) return;
	string ret=""; ret+=s[1]; int cur=0;
	for (i=2;i<n;++i)
	{
		if (s[i]!='?')
		{
			cur+=(ret.back()!=s[i]); ret+=s[i]; continue;
		}
		int tmp=k-(cur+(ret.back()!='0'));
		if (tmp%2==f[i+1][0].l%2&&f[i+1][0].l<=tmp&&tmp<=f[i+1][0].r)
		{
			cur+=(ret.back()!='0'); ret+='0'; continue;
		}
		if (--tmp,tmp%2==f[i+1][1].l%2&&f[i+1][1].l<=tmp&&tmp<=f[i+1][1].r)
		{
			cur+=(ret.back()!='0'); ret+='0'; continue;
		}
		tmp=k-(cur+(ret.back()!='1'));
		if (tmp%2==f[i+1][1].l%2&&f[i+1][1].l<=tmp&&tmp<=f[i+1][1].r)
		{
			cur+=(ret.back()!='1'); ret+='1'; continue;
		}
		if (--tmp,tmp%2==f[i+1][0].l%2&&f[i+1][0].l<=tmp&&tmp<=f[i+1][0].r)
		{
			cur+=(ret.back()!='1'); ret+='1'; continue;
		}
		return;
	}
	ret+=s[n]; ans=min(ans,ret);
}
int main()
{
	//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%s",&n,&k,s+1); ans="2";
		if (n==1)
		{
			if (k) puts("Impossible"); else
			{
				if (s[1]=='?') s[1]='0';
				putchar(s[1]); putchar('\n');
			}
			continue;
		}
		if (s[1]=='?'&&s[n]=='?')
		{
			s[1]='0'; s[n]='0'; solve();
			s[1]='0'; s[n]='1'; solve();
			s[1]='1'; s[n]='0'; solve();
			s[1]='1'; s[n]='1'; solve();
		} else if (s[1]=='?')
		{
			s[1]='0'; solve(); s[1]='1'; solve();
		} else if (s[n]=='?')
		{
			s[n]='0'; solve(); s[n]='1'; solve();
		} else solve();
		if (ans=="2") puts("Impossible"); else
		{
			for (RI i=0;i<ans.size();++i) putchar(ans[i]); putchar('\n');
		}
	}
	return 0;
}

L. Puzzle: Sashigane

小清新构造题

考虑我们初始时有一个\(1\times 1\)的正方形，我们考虑每一步把它的边长扩大\(1\)，这样只要贴着原来的正方形放一个两边等长的L形即可

不难发现每次至少存在一个方向扩展后是合法的，因此没有无解的情况

写的时候需要搞清楚题目中输出的规则，因此这题就没有讲给祁神写而是自己爬上去搓了下

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,xL,xR,yL,yR,vis[N][N];
inline bool check(CI r,CI c,CI h,CI w)
{
	if (r<1||r>n||c<1||c>n) return 0;
	if (h>0)
	{
		for (RI i=0;i<=h;++i) if (r+i<1||r+i>n||vis[r+i][c]) return 0;
	} else
	{
		for (RI i=h;i<=0;++i) if (r+i<1||r+i>n||vis[r+i][c]) return 0;
	}
	if (w>0)
	{
		for (RI i=0;i<=w;++i) if (c+i<1||c+i>n||vis[r][c+i]) return 0;
	} else
	{
		for (RI i=w;i<=0;++i) if (c+i<1||c+i>n||vis[r][c+i]) return 0;
	}
	return 1;
}
inline void paint(CI r,CI c,CI h,CI w)
{
	printf("%d %d %d %d\n",r,c,h,w);
	if (h>0)
	{
		for (RI i=0;i<=h;++i) vis[r+i][c]=1;
	} else
	{
		for (RI i=h;i<=0;++i) vis[r+i][c]=1;
	}
	if (w>0)
	{
		for (RI i=0;i<=w;++i) vis[r][c+i]=1;
	} else
	{
		for (RI i=w;i<=0;++i) vis[r][c+i]=1;
	}
}
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	scanf("%d%d%d",&n,&xL,&yL); xR=xL; yR=yL; vis[xL][yL]=1;
	puts("Yes"); printf("%d\n",n-1);
	for (RI len=1;len<n;++len)
	{
		if (check(xL-1,yL-1,len,len)) { paint(--xL,--yL,len,len); continue; }
		if (check(xR+1,yL-1,-len,len)) { paint(++xR,--yL,-len,len); continue; }
		if (check(xL-1,yR+1,len,-len)) { paint(--xL,++yR,len,-len); continue; }
		if (check(xR+1,yR+1,-len,-len)) { paint(++xR,++yR,-len,-len); continue; }
	}
	return 0;
}

M. Computational Geometry

好久没遇到计算几何了，但是无所谓祁神还是一样秒

这题其实很简单只要枚举固定的两个点的位置，中间部分的面积用前缀和算一下

而剩下一个点的最优选择很显然可以三分，然后这题就做完了

总复杂度\(O(n\log n)\)

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

const int N = 1e5+5;
int t, n, k;
struct Pt{
	int x, y;
	int crs(Pt b){return x*b.y-y*b.x;}	
	Pt operator-(const Pt b)const{return Pt{x-b.x, y-b.y};}
}pt[N*2];
__int128 pre[N*2];

int dis(Pt p, Pt a, Pt b){
	return abs((p-a).crs(b-a));
}

int bina(int l, int r){
	int L=l+1, R=r-1;
	while (L<R){
		int M1 = L+(R-L)/2;
		int M2 = M1 + 1;
//		printf("M1=%d M2=%d\n", M1, M2);
		if (dis(pt[M1], pt[l], pt[r])>dis(pt[M2], pt[l], pt[r])) R=M2-1;
		else L=M1+1;
	}
	return L;
}	

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--){
		cin >> n >> k;
		for (int i=0; i<n; ++i){
			cin >> pt[i].x >> pt[i].y;
			pt[n+i]=pt[i];
		}
		pt[n*2]=pt[0];
		for (int i=1; i<=n; ++i) pre[i]=pre[n+i]=pt[i-1].crs(pt[i]);
		for (int i=1; i<=n*2; ++i) pre[i]+=pre[i-1];
		__int128 ans=0;
		for (int i=0; i<n; ++i){
			__int128 sum1=pre[i+k]-pre[i] + pt[i+k].crs(pt[i]);
			int id=bina(i+k, i+n);
			sum1 += (pt[i+n]-pt[id]).crs(pt[i+k]-pt[id]);
//			printf("i=%d sum=%d\n", i, sum1);
			ans=max(ans, sum1);
		}
		if (ans%2==1) cout << (int)(ans/2) << ".5\n";
		else cout << (int)(ans/2) << '\n';
	}
	return 0;	
}