有什么好说的呢？

考试经过

T1智障题，写了一个小时结果边界判错挂成80;T2构造思路正确因为变量名写错挂成25
由于不知道checker的正确使用方式导致浪费了半个多小时搞这玩意
T3是个人都会几个\(log\)做法好像只有我打的暴力，连分块都能过我却一点梦想没有
T4因为贪部分分，用一发file error覆盖了48分暴力，像个小丑
预计得分280，实际得分130，很难不垫底
namespace_std出的题很好，然而这样感觉是浪费了一样

T1.谜之阶乘

水题
发现给出的数一定可以表示成连乘的形式，无非就是确定是几个数相乘以及从什么开始
首先他自己可以表示出来自己，这个直接算进答案
两个和三个数相乘的我用的二分，看是否有满足条件的整数解
四个数以上直接预处理，枚举所有乘积在\(10^{18}\)以内的数扔进map里
复杂度这样根本不是问题

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
map <int,int> p[20];
set <pair<int,int> >ans;
signed main()
{
	freopen("factorial.in","r",stdin);
	freopen("factorial.out","w",stdout);
	for(int i=4;i<=18;i++)
	{
		int s=1;for(int j=1;j<=i;j++)s=s*j;
		for(int j=i+1;j<=1e18;j++)
		{
			s/=(j-i);s*=j;
			if(s>1e18)break;
			p[i].insert(mp(s,j-i+1));
		}
	}
	int t;cin>>t;
	while(t--)
	{
		int x;scanf("%lld",&x);
		if(x==1){puts("-1");continue;}
		ans.clear();ans.insert(mp(x,x-1));
		int l=2,r=1e9,an=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(mid*(mid+1)==x){an=mid;break;}
			else if(mid*(mid+1)<x)l=mid+1;
			else r=mid-1;
		}
		if(an)ans.insert(mp(an+1,an-1));
		l=3,r=1e6,an=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(mid*mid*mid-mid==x){an=mid;break;}
			else if(mid*mid*mid-mid<x)l=mid+1;
			else r=mid-1;
		}
		if(an)ans.insert(mp(an+1,an-2));
		for(int i=4;i<=18;i++)
		{
			if(p[i].find(x)==p[i].end())continue;
			int ga=p[i][x];
			ans.insert(mp(ga+i-1,ga-1));
		}
		printf("%lld\n",(int)ans.size());
		for(auto it=ans.begin();it!=ans.end();it++)
			printf("%lld %lld\n",(*it).first,(*it).second);
	}
	return 0;
}

T2.子集

把\(n\)个数分成\(n/k\)组，每组\(k\)个数
发现如果组数是偶数，那么直接一正一反拼起来就行
奇数的话只需要处理三组，剩下的还是偶数
第一组\(1-n\)顺序排，第二组考虑将他往上拉一下，就是\(2,3,4,5,1\)这样
但不能拉少，应该使第三组可以拼成想要的答案才行，那么要拉多少可以一开始算出来
然后看还差多少填第三组，这样一定不重不漏，然后就是大模拟了
注意边界，注意特判

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000050;
vector <int> ans[N];
int n,k,lk,a[N],tot;
signed main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	int t;cin>>t;
	while(t--)
	{
		scanf("%lld%lld",&n,&k);
		int sum=((n+1)*n)/2;
		if(sum%k){puts("No");continue;}
		for(int i=1;i<=lk;i++)ans[i].clear();
		lk=k;int s=n/k;
		if(s&1)
		{	
			if(k==1)
			{
				puts("Yes");
				for(int i=1;i<=n;i++)printf("%lld ",i);
				puts("");continue;
			}
			if(s==1){puts("No");continue;}			
			for(int i=1;i<=s-3;i++)
			{
				int l=(i-1)*k+1,r=l+k-1;
				if(i&1)for(int j=1;j<=k;j++)ans[j].push_back(l+j-1);
				else for(int j=1;j<=k;j++)ans[j].push_back(l+(k-j+1)-1);
			}
			int ss=((k+1)*k)/2;ss*=3;assert(ss%k==0);int num=ss/k;
			int l=(s-3)*k+1,r=l+k-1,p=num-k-1;tot=0;
			for(int i=1;i<=k;i++)ans[i].push_back(l+i-1);
			l+=k;r+=k;
			for(int i=1;i<=k-p+1;i++)ans[i].push_back(l+(p+i-1)-1),a[++tot]=p+i-1;
			for(int i=k-p+2;i<=k;i++)ans[i].push_back(l+(i-(k-p+1))-1),a[++tot]=i-(k-p+1);
			l+=k;r+=k;
			for(int i=1;i<=k;i++)ans[i].push_back(l+num-a[i]-i-1);
		}
		else
		{
			for(int i=1;i<=s;i++)
			{
				int l=(i-1)*k+1,r=l+k-1;
				if(i&1)for(int j=1;j<=k;j++)ans[j].push_back(l+j-1);
				else for(int j=1;j<=k;j++)ans[j].push_back(l+(k-j+1)-1);
			}	
		}
		puts("Yes");
		for(int i=1;i<=k;i++)
		{
			for(int j=0;j<ans[i].size();j++)
				printf("%lld ",ans[i][j]);
			putchar('\n');
		}
	}
	return 0;	
}

T3.混凝土粉末

转化问题是区间加，询问一个位置最早大于等于\(y\)是什么时候
正解是一种神仙的离线方式，以时间为下标开树状数组，然后把询问和修改都挂到原序列上
然后扫原序列，对于一个修改，在扫到左端点的时候插入，右端点删除
在插入之后，删除之前回答询问，这里采用了一手nb的树状数组上倍增
就是求前缀和大于等于\(x\)的最小下标之类，类比一下树上倍增，理解了树状数组的原理还是不难的
考场不会系列，啥时候数据结构能爱我啊

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000060;
int n,q;
struct bit{
	int b[N];
	inline int lowbit(int x){return x&(-x);}
	inline void add(int p,int v)
	{
		for(int i=p;i<=q;i+=lowbit(i))	
			b[i]+=v;
	}
	inline int get(int lim,int v)
	{
		int x=0;
		for(int i=20;i>=0;i--)
		{
			if((x|(1<<i))<=lim&&b[x|(1<<i)]<v)x|=1<<i,v-=b[x];
		}
		if(x==lim)return 0;
		else return x+1;
	}
}tr;
vector <pair<int,int> > p1[N],p2[N],p3[N];
int ans[N],op[N];
signed main()
{		
	freopen("concrete.in","r",stdin);
	freopen("concrete.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=q;i++)
	{	
		scanf("%lld",&op[i]);
		if(op[i]&1)
		{
			int x,l,r;scanf("%lld%lld%lld",&l,&r,&x);
			p1[l].push_back(make_pair(i,x));
			p2[r].push_back(make_pair(i,x));	
		}
		else
		{
			int x,y;scanf("%lld%lld",&x,&y);
			p3[x].push_back(make_pair(i,y));
		}	
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<p1[i].size();j++)tr.add(p1[i][j].first,p1[i][j].second);
		for(int j=0;j<p3[i].size();j++)ans[p3[i][j].first]=tr.get(p3[i][j].first,p3[i][j].second);
		for(int j=0;j<p2[i].size();j++)tr.add(p2[i][j].first,-p2[i][j].second);
	}
	for(int i=1;i<=q;i++)if(!(op[i]&1))printf("%lld\n",ans[i]);
	return 0;
}

T4.排水系统

和原题不一样的是有了一个损坏值，还有概率，让求期望
如果一个管坏了相当于从\(x\)到\(y\)减少了，从\(x\)到其他的贡献增加了
那么可以算出来该加减多少，由于其他都增加可以视为\(x\)增加，所以乘个概率就行
然而你直接写会有36的高分，注意这里的流量是相对与啥也不坏的情况而言的，所以应该先做一边算出啥也不坏是每个的流量\(s1\)，再以\(s1\)为基数执行上面的该加加该减减，然后就好了

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int M=500050,N=200050;
const int mod=998244353;
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
struct node{
	int from,to,next,w;
}a[M];
int head[N],mm=1;
inline void add(int x,int y,int z)
{
	a[mm].from=x;a[mm].to=y;a[mm].w=z;
	a[mm].next=head[x];head[x]=mm++;
}
int n,m,r,k,du[N],to[N],s[N],ss[N],duu[N];
int inv[M],ga,sum;queue <int> q;
inline void gankp1()
{
	memcpy(duu,du,sizeof(duu));
	for(int i=1;i<=n;i++)if(!duu[i])q.push(i);	
	while(q.size())
	{
		int x=q.front(),w=ss[x]*inv[to[x]]%mod;q.pop();
		for(int i=head[x];i;i=a[i].next)
		{
			int y=a[i].to;ss[y]=(ss[y]+w)%mod;
			duu[y]--;if(!duu[y])q.push(y);
		}
	}	
}
inline void gankp2()
{	
	for(int i=1;i<=n;i++)if(!du[i])q.push(i);
	while(q.size())
	{
		int x=q.front(),w=ss[x],num=to[x];q.pop();
		int p1=w*inv[num]%mod,p2=w*inv[num-1]%mod,pp=(p2-p1+mod)%mod;
		for(int i=head[x];i;i=a[i].next)
		{		
			int y=a[i].to,p=a[i].w*ga%mod;
			s[x]=(s[x]+p*pp%mod*num%mod)%mod;
			s[y]=(s[y]-(pp+p1)%mod*p%mod+mod)%mod;
		}
		for(int i=head[x];i;i=a[i].next)
		{
			int y=a[i].to;s[y]=(s[y]+s[x]*inv[num]%mod)%mod;
			du[y]--;if(!du[y])q.push(y);
		}
	}
}	
signed main()
{
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	cin>>n>>m>>r>>k;
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read(),w=read();
		add(x,y,w);du[y]++;to[x]++;sum=(sum+w)%mod;
	}
	for(int i=1;i<=m;i++)s[i]=ss[i]=1;
	inv[0]=inv[1]=1;for(int i=2;i<=k;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	ga=ksm(sum,mod-2);gankp1();gankp2();
	for(int i=n-r+1;i<=n;i++)printf("%lld ",s[i]);
	return 0;
}

考试总结

感觉问题还是很大，尤其是自己感觉很好但结果很差的时候
不能指着自己像CSP一样想到啥就有啥，应该求稳，要拍，要看边界
应该也是学到了不少，那么下一场就要注意了