Preface

最唐氏的一集，尽情欣赏ABC E题战俘的丑态

这场打的时候就很抽象，各种傻逼错误频发，从B题一路WA到G题

还好发现E后面的题更简单后马上把FG写了，不然要爆炸了

A - Chord

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int INF=1e9;
string s;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	cin>>s;
	if (s=="ACE"||s=="BDF"||s=="CEG"||s=="DFA"||s=="EGB"||s=="FAC"||s=="GBD")
	puts("Yes"); else puts("No"); return 0;
}

B - TaK Code

签到，因为一个地方\(m\)打成\(n\)了WA了一发

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=105,INF=1e9;
int n,m; char a[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,p,q; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",a[i]+1);
	for (i=1;i+8<=n;++i) for (j=1;j+8<=m;++j)
	{
		int cur=0; for (p=1;p<=3;++p) for (q=1;q<=3;++q)
		{
			if (a[i+p-1][j+q-1]=='#') ++cur;
			if (a[i+8-p+1][j+8-q+1]=='#') ++cur;
		}
		if (cur!=18) continue;
		for (cur=0,p=1;p<=4;++p) if (a[i+3][j+p-1]=='.') ++cur;
		for (p=1;p<=3;++p) if (a[i+p-1][j+3]=='.') ++cur;
		for (p=1;p<=4;++p) if (a[i+5][j+8-p+1]=='.') ++cur;
		for (p=1;p<=3;++p) if (a[i+8-p+1][j+5]=='.') ++cur;
		if (cur!=14) continue;
		printf("%d %d\n",i,j);
	}
	return 0;
}

C - Invisible Hand

签到，直接二分答案即可，但要注意答案的上界是\(10^9+1\)而非\(10^9\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005,INF=1e9;
int n,m,a[N],b[N];
inline bool check(CI x)
{
	RI i; int c1=0,c2=0; for (i=1;i<=n;++i) c1+=(a[i]<=x);
	for (i=1;i<=m;++i) c2+=(x<=b[i]); return c1>=c2;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=m;++i) scanf("%d",&b[i]);
	int l=0,r=INF+1,mid,ret; while (l<=r)
	if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
	return printf("%d",ret),0;
}

D - Count Bracket Sequences

先经典地把(看作\(1\)，)看作\(-1\)

注意到字符串长度很小，因此可以直接暴力DP，设\(f_{i,j}\)表示处理了前\(i\)个位置，前缀和为\(j\)的方案数

转移很trivial，注意所有\(j<0\)的状态都不合法即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=3005,mod=998244353;
int n,f[N][N]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%s",s+1),n=strlen(s+1),f[0][0]=i=1;i<=n;++i) for (j=0;j<=i-1;++j)
	{
		if (s[i]=='(') (f[i][j+1]+=f[i-1][j])%=mod; else
		if (s[i]==')')
		{
			if (j>0) (f[i][j-1]+=f[i-1][j])%=mod;
		} else
		{
			(f[i][j+1]+=f[i-1][j])%=mod;
			if (j>0) (f[i][j-1]+=f[i-1][j])%=mod;
		}
	}
	return printf("%d",f[n][0]),0;
}

E - Tangency of Cuboids

原来是个暴力题，比赛的时候究极降智

这题乍一看很吓人，其实只要发现对于每一个面的每一个\(1\times 1\)的小正方形，覆盖它的最多只有两个长方体，否则就会出现体积相交的情况

由于值域也很小，那么直接暴力维护下每个面的每个小正方形对应的编号即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=105;
int n,a,b,c,d,e,f; vector <int> XOY[N][N][N],XOZ[N][N][N],YOZ[N][N][N]; set <int> rst[100005];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,s; for (scanf("%d",&n),s=1;s<=n;++s)
	{
		scanf("%d%d%d%d%d%d",&a,&c,&e,&b,&d,&f);
		for (i=a;i<b;++i) for (j=c;j<d;++j) XOY[i][j][e].push_back(s),XOY[i][j][f].push_back(s);
		for (i=a;i<b;++i) for (j=e;j<f;++j) XOZ[i][c][j].push_back(s),XOZ[i][d][j].push_back(s);
		for (i=c;i<d;++i) for (j=e;j<f;++j) YOZ[a][i][j].push_back(s),YOZ[b][i][j].push_back(s);
	}
	for (i=0;i<=100;++i) for (j=0;j<=100;++j) for (k=0;k<=100;++k)
	for (auto x:XOY[i][j][k]) for (auto y:XOY[i][j][k]) if (x!=y) rst[x].insert(y);
	for (i=0;i<=100;++i) for (j=0;j<=100;++j) for (k=0;k<=100;++k)
	for (auto x:XOZ[i][j][k]) for (auto y:XOZ[i][j][k]) if (x!=y) rst[x].insert(y);
	for (i=0;i<=100;++i) for (j=0;j<=100;++j) for (k=0;k<=100;++k)
	for (auto x:YOZ[i][j][k]) for (auto y:YOZ[i][j][k]) if (x!=y) rst[x].insert(y);
	for (i=1;i<=n;++i) printf("%d\n",rst[i].size());
	return 0;
}

F - Cans and Openers

由于\(1,2\)类物品要配合使用而\(0\)类物品相对独立，因此考虑先枚举确定\(0\)类物品操作的个数，先贪心地取走这部分较大的那些物品

剩下的其实就是要求出对于不同的操作次数，怎么用\(1,2\)类物品是最优的，可以用如下的贪心策略来解决

首先给两类物品均从大到小排序，第一个操作肯定是选一个\(2\)类物品，我们考虑记录此时剩余可以打开的\(1\)类物品数量

再枚举操作次数，如果此时还有可以打开的\(1\)类物品就直接打开，否则就选一个\(2\)类物品打开，不难发现这样一定是最优的

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

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,m,tp,x,a[N],pa,b[N],pb,c[N],pc; LL pfx_a[N],pfx_b[N],pfx_c[N],f[N],ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
	{
		scanf("%d%d",&tp,&x); if (tp==0) a[++pa]=x;
		else if (tp==1) b[++pb]=x; else c[++pc]=x;
	}
	sort(a+1,a+pa+1,greater <int>());
	sort(b+1,b+pb+1,greater <int>());
	sort(c+1,c+pc+1,greater <int>());
	for (i=1;i<=pa;++i) pfx_a[i]=pfx_a[i-1]+a[i];
	for (i=1;i<=pb;++i) pfx_b[i]=pfx_b[i-1]+b[i];
	for (i=1;i<=pc;++i) pfx_c[i]=pfx_c[i-1]+c[i];
	for (j=1,i=2;i<=m;++i)
	{
		if (pfx_c[j]<i-j) ++j;
		f[i]=(j<=pc?pfx_b[min(pb,i-j)]:pfx_b[min(1LL*pb,pfx_c[pc])]);
	}
	for (i=0;i<=pa&&i<=m;++i) ans=max(ans,pfx_a[i]+f[m-i]);
	return printf("%lld",ans),0;
}

G - Avoid Straight Line

纯纯的送分题，考虑容斥，用\(C_n^3\)减去所有构成路径的三元组即可

考虑统一在每条路径的中间那个点处统计答案，对于点\(x\)，它要减去的贡献就是它所有子树以及子树外之间两两构成的路径条数，这是个很经典的东西

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

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,x,y,sz[N]; vector <int> v[N]; LL ans;
inline void DFS(CI now=1,CI fa=0)
{
	sz[now]=1; for (int to:v[now]) if (to!=fa) DFS(to,now),sz[now]+=sz[to];
	int ret=n-sz[now]; for (int to:v[now]) if (to!=fa) ans-=1LL*ret*sz[to],ret+=sz[to];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	if (n<3) return puts("0"),0; ans=1LL*n*(n-1)*(n-2)/6LL;
	return DFS(),printf("%lld",ans),0;
}