Preface
今天这场签到巨多，和昨天那场形成了鲜明的对比
但可惜后盘的时候我划了太久的水，最后接了B题然后没调出来成为战俘
最气的是赛后发现原来是没注意输出格式，本来可以说一遍过的题结果没写过，属实可惜，就当长教训了
以后一定要尤其注意输入输出格式
A. Asking for Money
ORZ 徐神
设点\(p\)的两个出点为\(a,b\)，考虑什么时候\(p\)会亏钱，显然是存在某个点可以在不经过\(p\to a,p\to b\)这两条边的同时到达\(p,a,b\)三个点时
直接暴力处理的话复杂度是\(O(n^3)\)的，不妨考虑把图反过来建，转化为求三个点能到达的公共点，复杂度就变成\(O(n^2)\)了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
int n, indu[1001];
std::vector<int> out[1001], back[1001];
std::bitset<1001> vis[3];
void dfs(int now, std::bitset<1001> &vis) {
vis[now] = 1;
for(int back: back[now]) if(!vis[back]) dfs(back, vis);
};
bool check(int c) {
for(int i = 0; i < 2; ++i) {
vis[i].reset() , vis[i][c] = 1;
dfs(out[c][i], vis[i]), vis[i][c] = 0;
}
vis[2].reset(), dfs(c, vis[2]); vis[2][c] = 0;
return (vis[0] & vis[1] & vis[2]).any();
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) for(int j = 0, to; j < 2; ++j) {
scanf("%d", &to); out[i].push_back(to); back[to].push_back(i);
indu[i] += 1;
}
for(int i = 1; i <= n; ++i) putchar(indu[i] && check(i) ? 'Y' : 'N');
putchar(10);
return 0;
}
B. Board Game
很套路的一个题，类似思想的东西之前写过好多遍了，今天其实已经很快地写出来了但就是失了智没有把点排序再输出
考虑以直线的序号为下标建立线段树，对于一个给定的\(X\)，考虑我们已知每个区间\([l,r]\)中所有直线中，\(AX+B\)的最大值
那么我们就可以用线段树上二分来找到对于每个点，在它上面的序号最小的直线是哪条了，只要根据这个最大值和\(Y\)的大小关系进行讨论即可
考虑怎么维护求\(AX+B\)最大值的东西，这个就是个经典套路了，我们把区间内所有直线构成的半平面求出来（等价于一个下凸壳），同时顺带维护下交点的坐标
那么对于给定的\(X\)，只要二分求出它在哪条线段上即可，当然这里我们可以把询问点按照\(x\)升序排列，这样最优的决策线段的移动就是单调的，复杂度降为\(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>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
struct Point
{
int x,y,id;
inline Point(CI X=0,CI Y=0,CI ID=0)
{
x=X; y=Y; id=ID;
}
friend inline bool operator < (const Point& A,const Point& B)
{
return A.x!=B.x?A.x<B.x:A.y<B.y;
}
}P[N]; int n,m; vector <int> ans[N];
struct line
{
int a,b;
inline line(CI A=0,CI B=0)
{
a=A; b=B;
}
friend inline bool operator < (const line& A,const line& B)
{
return A.a!=B.a?A.a<B.a:A.b<B.b;
}
inline int get(CI x)
{
return a*x+b;
}
}L[N];
inline double get_x(const line& L1,const line& L2)
{
if (L1.a==L2.a) return -1e18;
return 1.0*(L2.b-L1.b)/(L1.a-L2.a);
}
class Segment_Tree
{
private:
vector <double> p[N<<2]; vector <line> stk[N<<2]; int t[N<<2];
inline int calc(CI now,CI X)
{
while (t[now]<(int)p[now].size()&&p[now][t[now]]<=X) ++t[now];
return stk[now][t[now]].get(X);
}
public:
#define TN CI now=1,CI l=1,CI r=m
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
vector <line> tmp; for (RI i=l;i<=r;++i) tmp.push_back(L[i]);
sort(tmp.begin(),tmp.end());
for (auto it:tmp)
{
if (stk[now].size()<=1)
{
stk[now].push_back(it);
if (stk[now].size()==2) p[now].push_back(get_x(stk[now][0],stk[now][1]));
continue;
}
while (p[now].size()&&get_x(it,stk[now].back())<=p[now].back())
p[now].pop_back(),stk[now].pop_back();
stk[now].push_back(it); p[now].push_back(get_x(stk[now].back(),stk[now][stk[now].size()-2]));
}
if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
}
inline void query(CI X,CI Y,CI id,TN)
{
if (calc(now,X)<=Y) return;
if (l==r) return ans[l].push_back(id); int mid=l+r>>1;
if (calc(now<<1,X)>Y) query(X,Y,id,LS); else query(X,Y,id,RS);
}
#undef TN
#undef LS
#undef RS
}SEG;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld%lld",&P[i].x,&P[i].y),P[i].id=i;
for (scanf("%lld",&m),i=1;i<=m;++i) scanf("%lld%lld",&L[i].a,&L[i].b);
for (SEG.build(),sort(P+1,P+n+1),i=1;i<=n;++i) SEG.query(P[i].x,P[i].y,P[i].id);
for (i=1;i<=m;++i)
{
printf("%lld ",ans[i].size());
sort(ans[i].begin(),ans[i].end());
for (int x:ans[i]) printf("%lld ",x);
putchar('\n');
}
return 0;
}
C. City Folding
正着考虑很麻烦，考虑倒着推出该数在上半层还是下半层然后就很好处理了
具体实现需要一些细节，代码是徐神写的
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using llsi = long long signed int;
llsi n, p, h;
bool turn_over[64];
char ans[64];
int main() {
std::cin >> n >> p >> h;
for(llsi i = n - 1ll; ~i; --i) {
if(h > (1ll << i)) turn_over[i] = 1, h = (1ll << (i + 1ll)) - h + 1ll;
else turn_over[i] = 0;
}
for(llsi i = 0ll, l = 1ll << (n - 1ll); i < n; ++i, l >>= 1ll) {
if(p <= l) {
if(turn_over[i]) {
ans[i] = 'L';
p = l - p + 1ll;
} else {
ans[i] = 'R';
p = p;
}
} else {
if(turn_over[i]) {
ans[i] = 'R';
p = 2ll * l - p + 1ll;
} else {
ans[i] = 'L';
p = p - l;
}
}
}
for(int i = 0ll; i < n; ++i) putchar(ans[i]);
putchar(10);
return 0;
}
D. Daily Trips
签到题，题意我都不知道，又被徐神秒了
#include <cstdio>
#include <cstring>
#include <algorithm>
using llsi = long long signed int;
int n, h, w;
char mygetc() {
static char c[3]; scanf("%s", c); return c[0];
}
int main() {
scanf("%d%d%d", &n, &h, &w);
for(int i = 1; i <= n; ++i) {
char c = mygetc();
if(c == 'Y' || w == 0) h -= 1, w += 1, printf("Y ");
else printf("N ");
c = mygetc();
if(c == 'Y' || h == 0) w -= 1, h += 1, printf("Y\n");
else printf("N\n");
}
return 0;
}
E. Empty Squares
开场开这题分类讨论然后WA on 85，后面仔细一想数据范围不大干脆写个DP算了
设\(f_{i,j}\)表示左边放了长为\(i\)的砖，右边放了长为\(j\)的砖的状态是否可达，转移就类似于背包
#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>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int n,k,L,R,ans; bool f[N][N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,s; scanf("%d%d%d",&n,&k,&L); R=n-L-k;
for (f[0][0]=s=1;s<=n;++s) if (s!=k)
for (i=L;i>=0;--i) for (j=R;j>=0;--j)
{
if (i>=s) f[i][j]|=f[i-s][j];
if (j>=s) f[i][j]|=f[i][j-s];
}
for (i=0;i<=L;++i) for (j=0;j<=R;++j)
if (f[i][j]) ans=max(ans,i+j+k);
return printf("%d",n-ans),0;
}
F. Favorite Tree
这题题意很坑，subtree指的是树中的联通块而非子树
这题一眼树Hash，但众所周知树Hash只能做子树问题而不能做一般的连通块，因此只能另辟蹊径
首先将T2的根定为\(1\)，考虑枚举T1的根\(i\)，并假设\(i\)和\(1\)配对，然后考虑DP
设\(f_{i,j}\)表示将T1中的\(i\)和T2中的\(j\)配对是否可行，检验的话需要枚举\(i,j\)的子节点
若\(f_{son(i),son(j)}\)为\(1\)的话就连一条\(son(i)\to son(j)\)的边，然后跑二分图匹配看看是否存在完美匹配，若存在即说明\(f_{i,j}\)合法
用Dinic实现二分图匹配，总复杂度\(O(n^3\sqrt 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>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int n1,n2,x,y,f[N][N],idx[N],idy[N]; vector <int> T1[N],T2[N];
namespace Network_Flow
{
const int NN=205,MM=1e7+5,INF=1e9;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[N],cur[N],dep[N],s,t; queue <int> q;
inline void addedge(CI x,CI y,CI z)
{
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,t+1<<2); dep[s]=1; q=queue <int>(); q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=0; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,t+1<<2),ret+=DFS(s,t,INF); return ret;
}
inline void clear(void)
{
for (RI i=1;i<=t;++i) head[i]=0; cnt=1;
}
};
using namespace Network_Flow;
inline int DP(CI x,CI y,CI fx=0,CI fy=0)
{
if (~f[x][y]) return f[x][y];
int chx=T1[x].size()-(fx!=0),chy=T2[y].size()-(fy!=0);
if (!chy) return f[x][y]=1; if (chx<chy) return f[x][y]=0;
for (int sx:T1[x]) if (sx!=fx)
for (int sy:T2[y]) if (sy!=fy) DP(sx,sy,x,y);
int cntx=0,cnty=0;
for (int sx:T1[x]) if (sx!=fx) idx[sx]=++cntx;
for (int sy:T2[y]) if (sy!=fy) idy[sy]=++cnty;
s=chx+chy+1; t=s+1; clear();
for (int sx:T1[x]) if (sx!=fx) addedge(s,idx[sx],1);
for (int sy:T2[y]) if (sy!=fy) addedge(chx+idy[sy],t,1);
for (int sx:T1[x]) if (sx!=fx)
for (int sy:T2[y]) if (sy!=fy)
if (DP(sx,sy,x,y)) addedge(idx[sx],chx+idy[sy],1);
return f[x][y]=(Dinic()==chy);
}
inline void DEBUG(void)
{
for (RI i=1;i<=n1;++i) for (RI j=1;j<=n2;++j)
printf("f[%d][%d] = %d\n",i,j,f[i][j]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n1),i=1;i<n1;++i)
scanf("%d%d",&x,&y),T1[x].push_back(y),T1[y].push_back(x);
for (scanf("%d",&n2),i=1;i<n2;++i)
scanf("%d%d",&x,&y),T2[x].push_back(y),T2[y].push_back(x);
for (i=1;i<=n1;++i)
{
memset(f,-1,sizeof(f));
if (DP(i,1)) return puts("Y"),0;
}
return puts("N"),0;
}
G. Gravitational Wave Detector
ORZ 祁神，秒切计算几何题给我们队拉回一题，否则要被血虐了
假设\(a\in P,b\in Q\)，另外一个点\(c\)为中点，此时我们得到\(2c=a+b\)，不难发现求出\(P,Q\)的闵可夫斯基然后判断点是否在凸包内即可
而另外两种情况例如\(a\)为中点时，我们有\(c=2a-b\)，同样求出右边的闵可夫斯基和然后检验即可，另一种情况也是同理
但是要注意精度以及点共线的情况，算是计算几何的常态了
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e5+5;
inline int read(){
int x=0, f=1; char ch=getchar();
while (!isdigit(ch)&&'-'!=ch) ch=getchar();
if ('-'==ch) f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
return x*f;
}
void write(int x){
if (x>9) write(x/10);
putchar('0'+x%10);
}
int q;
struct Pt{
int x, y;
bool operator<(const Pt b)const{ return x==b.x ? y<b.y : x<b.x;}
bool operator>(const Pt b)const{ return x==b.x ? y>b.y : x>b.x;}
Pt operator+(const Pt b)const{ return Pt{x+b.x, y+b.y}; }
Pt operator-(const Pt b)const{ return Pt{x-b.x, y-b.y}; }
Pt operator*(const int d)const{ return Pt{x*d, y*d}; }
};
vector<Pt> poly[2];
vector<Pt> res1, res2, res3;
vector<Pt> tmp1, tmp2, tmp3, tmp4;
int dn[2], mn[2], sz[2];
int cross(Pt a, Pt b){ return a.x*b.y-a.y*b.x; }
int sgn(int x){ return 0==x ? 0 : (x>0 ? 1 : -1);}
// double dist(Pt a, Pt b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool inPoly(vector<Pt> &poly, const Pt p){
int sz = poly.size();
Pt v = p-poly[0];
if (cross(poly[1]-poly[0],v)<0 || cross(poly[sz-1]-poly[0], v)>0) return false;
int L=1, R=sz-1;
while (L+1<R){
int M = L+(R-L)/2;
if (cross(poly[M]-poly[0], v)<=0) R=M;
else L=M;
}
if (cross(poly[L+1]-poly[L], p-poly[L])<0) return false;
else return true;
}
void findminco(vector<Pt> &minco, vector<Pt> &p0, int mn0, vector<Pt> &p1, int mn1){
int sz0=p0.size(), sz1=p1.size();
minco.push_back(p0[mn0]+p1[mn1]);
int cur0=0, cur1=0;
for (int i=1; i<=sz0+sz1; ++i){
if (cur0<sz0 && cur1<sz1){
Pt l0 = p0[(mn0+cur0+1)%sz0] - p0[(mn0+cur0)%sz0];
Pt l1 = p1[(mn1+cur1+1)%sz1] - p1[(mn1+cur1)%sz1];
if (cross(l0, l1) >= 0) minco.push_back(l0), ++cur0;
else minco.push_back(l1), ++cur1;
}else{
if (cur0<sz0) minco.push_back(p0[(mn0+cur0+1)%sz0] - p0[(mn0+cur0)%sz0]), ++cur0;
else minco.push_back(p1[(mn1+cur1+1)%sz1] - p1[(mn1+cur1)%sz1]), ++cur1;
}
}
int cur=0;
for (int i=1; i<=sz0+sz1; ++i){
if (0==cross(minco[cur]-minco[cur-1], minco[i])) minco[cur]=minco[cur]+minco[i];
else minco[cur+1] = minco[cur] + minco[i], ++cur;
}
minco.erase(minco.begin()+cur, minco.end());
// minco.push_back(poly[0][mn0]+poly[1][mn1]);
// dn=0;
// for (int i=1; i<=n+m; i++){
// // printf("cur0=%d cur1=%d\n", cur0, cur1);
// if (cur0<n && cur1<m){
// Pt p0 = poly[0][(mn0+cur0+1)%n]-poly[0][(mn0+cur0)%n];
// Pt p1 = poly[1][(mn1+cur1+1)%m]-poly[1][(mn1+cur1)%m];
// // printf("p0(%d, %d) p1(%d, %d)\n", p0.x, p0.y, p1.x, p1.y);
// if (cross(p0, p1) >= 0) minco.push_back(p0), ++cur0;
// else minco.push_back(p1), ++cur1;
// }else{
// if (cur0<n) minco.push_back(poly[0][(mn0+cur0+1)%n]-poly[0][(mn0+cur0)%n]), ++cur0;
// else minco.push_back(poly[1][(mn1+cur1+1)%m]-poly[1][(mn1+cur1)%m]), ++cur1;
// }
// }
// for (int i=1; i<=m+n; i++){
// minco[i] = minco[i]+minco[i-1];
// if ((minco[i].x > minco[dn].x) || (minco[i].x==minco[dn].x && minco[i].y>minco[dn].y))
// dn=i;
// }
// minco.pop_back();
}
signed main(){
int mn0=0, mn1=0;
for (int d=0; d<2; ++d){
sz[d]=read();
poly[d].resize(sz[d]);
for (int i=0; i<sz[d]; i++){
poly[d][i].x=read(), poly[d][i].y=read();
if (poly[d][i].x < poly[d][mn[d]].x) mn[d]=i;
else if (poly[d][i].x == poly[d][mn[d]].x && poly[d][i].y < poly[d][mn[d]].y) mn[d]=i;
if (poly[d][i].x > poly[d][dn[d]].x) dn[d]=i;
else if (poly[d][i].x == poly[d][dn[d]].x && poly[d][i].y > poly[d][dn[d]].y) dn[d]=i;
}
}
for (auto p : poly[0]){
tmp1.push_back(p*2);
tmp3.push_back(Pt{0, 0}-p);
}
for (auto p : poly[1]){
tmp2.push_back(Pt{0, 0}-p);
tmp4.push_back(p*2);
}
findminco(res1, poly[0], mn[0], poly[1], mn[1]);
findminco(res2, tmp1, mn[0], tmp2, dn[1]);
findminco(res3, tmp3, dn[0], tmp4, mn[1]);
// printf("res1\n");
// for (auto p : res1) printf("(%d %d)\n", p.x, p.y);
// printf("res1\n");
// for (auto p : res2) printf("(%d %d)\n", p.x, p.y);
// printf("res1\n");
// for (auto p : res3) printf("(%d %d)\n", p.x, p.y);
q=read();
while (q--){
Pt pp;
pp.x=read(); pp.y=read();
if (inPoly(res1, pp*2) || inPoly(res2, pp) || inPoly(res3, pp)) putchar('Y');
else putchar('N');
}puts("");
// while (1){}
return 0;
}
H. Horse Race
考虑求出每匹马最后可能的排名集合，只要将马和排名连边后跑个最大匹配即可得到答案
刚开始很容易想到对于每个限制，给出的所有马的最小排名都要被更新为给出的排名，但这样只能保证不等号成立而不能保证取等
解决方法就是把剩余不在集合中的马可能的排名集合中对应的排名删除掉，这样就能保证至少其中一匹马取得给出的排名了
#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>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=305;
int n,m,k,rk,vis[N],match[N],mx[N],invalid[N][N],ext[N];
string s,name[N]; map <string,int> rst; vector <int> v[N];
inline bool find(CI now,CI idx)
{
for (int to:v[now]) if (vis[to]!=idx)
{
vis[to]=idx;
if (!match[to]||find(match[to],idx))
return match[to]=now,1;
}
return 0;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
std::ios::sync_with_stdio(false);
RI i,j; for (cin>>n,i=1;i<=n;++i) cin>>name[i],rst[name[i]]=i,mx[i]=1;
for (cin>>m,i=1;i<=m;++i)
{
for (cin>>k>>rk,j=1;j<=k;++j) cin>>s,ext[rst[s]]=1;
for (j=1;j<=n;++j) if (ext[j]) mx[j]=max(mx[j],rk); else invalid[j][rk]=1;
for (j=1;j<=n;++j) ext[j]=0;
}
for (i=1;i<=n;++i) for (j=mx[i];j<=n;++j)
if (!invalid[i][j]) v[i].push_back(j);
for (i=1;i<=n;++i) find(i,i);
for (i=1;i<=n;++i) cout<<name[match[i]]<<' ';
return 0;
}
I. Italian Calzone & Pasta Corner
签到，祁神写的，我至今也不知道题意
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 105;
inline int read(){
int x=0, f=1; char ch=getchar();
while (!isdigit(ch)&&'-'!=ch) ch=getchar();
if ('-'==ch) f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
return x*f;
}
int n, m;
int mp[N][N];
bool vis[N][N];
pair<int, int> pos[N*N];
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
signed main(){
n=read(); m=read();
int cur=0;
for (int i=1; i<=n; ++i){
for (int j=1; j<=m; ++j){
mp[i][j]=read();
int x = mp[i][j];
pos[x].first=i, pos[x].second=j;
}
}
int res=0;
for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j){
priority_queue<int, vector<int>, greater<int>> Q;
Q.push(mp[i][j]);
int ans=0;
memset(vis, 0, sizeof(vis));
// printf("i=%d j=%d\n", i, j);
while (!Q.empty()){
int x = Q.top(); Q.pop();
// printf("x=%d\n", x);
int r=pos[x].first, c=pos[x].second;
++ans;
for (int d=0; d<4; ++d){
int nr = r+dir[d][0], nc=c+dir[d][1];
if (nr<=0 || nr>n || nc<=0 || nc>m || vis[nr][nc]) continue;
if (mp[nr][nc] > mp[r][c]){
Q.push(mp[nr][nc]);
vis[nr][nc]=true;
}
}
}
res = max(res, ans);
}
printf("%d\n", res);
// while (1){}
return 0;
}
J. Joining a Marathon
不可做题，弃了弃了
K. Kind Baker
徐神，构造的king！
首先发现要用的最少机器数为\(n=\lceil\log_2 k\rceil\)，而这道题的难点其实就在于如何用\(n\)个机器做出\(2^n\)种不同的蛋糕，后面剩余的部分其实很好处理
刚开始有一个naive的想法就是先把第一行全部加上所有调料，然后在第二行间隔\(2^t\)放不同的调料即可
但这样需要的格子数量为\(2\times 2^n\)，显然不符合题意
可我们发现我们可以把其它行也利用起来，只要先把第一行和第一列加上所有调料，这样后面的所有区域都可以使用了，再用上面的思路来做即可
代码有很多细节，写的徐神频频口吐芬芳
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using llsi = long long signed int;
using pii = std::pair<int, int>;
int k, c;
int t[101][101];
int cnt[10000], tot = 0;
std::vector<pii> v[101];
int main() {
scanf("%d", &k);
k -= 1;
for(c = 0; (1 << c) < k; ++c);
if(1 << c == k) t[100][100] = 1 << c, k -= 1;
for(int i = 1; i <= 99; ++i) t[i][1] = (1 << c) - 1;
for(int i = 1; i <= 99; i += 2) for(int j = 2; j <= 99; ++j) t[i][j] = (1 << c) - 1;
for(int i = 0; i < k; ++i) {
int x = (i / 98 + 1) * 2, y = i % 98 + 2;
t[x][y] = i;
}
for(int i = 1; i <= 100; ++i) for(int j = 1; j <= 100; ++j) {
cnt[t[i][j]] = 1;
for(int k = 0; k < 30; ++k) if((1 << k) & t[i][j]) v[k].push_back({i, j});
}
c = 0; for(int i = 0; i <= 100; ++i) c += bool(v[i].size());
// {
// for(int i = 1; i <= 100; ++i) for(int j = 1; j <= 100; ++j) printf("%d%c", t[i][j], j == 100 ? 10 : 32);
// for(int i = 0; i < 10000; ++i) tot += cnt[i]; fprintf(stderr, "%d\n", tot);
// fprintf(stderr, "c = %d\n", c);
// return 0;
// }
printf("%d\n", c);
for(int i = 0; i <= 100; ++i) if(v[i].size()) {
printf("%d", (int)v[i].size());
for(auto [x, y]: v[i]) printf(" %d %d", x, y);
puts("");
}
if(v[c].size()) fputs("FUCK", stderr);
return 0;
}
L. Lazy Printing
又是徐神写的，这么一看这场我写的题好少
据说是个KMP一眼题，但我连题目都没看
#include <cstdio>
#include <cstring>
#include <algorithm>
using llsi = long long signed int;
constexpr int $n = 200000 + 5;
int fail[$n], d, ans = 0;
char* kmp(char *s) {
fail[0] = fail[1] = 0;
int i, j;
for(i = 2, j = 0; s[i]; ++i) {
while(j && s[j + 1] != s[i]) j = fail[j];
if(s[j + 1] == s[i]) j += 1;
fail[i] = j;
if(i - fail[i] > d) break;
}
return s + i;
}
char s[$n];
int main() {
scanf("%s%d", s, &d);
for(char *l = s; *l; ++ans, l = kmp(l - 1));
printf("%d\n", ans);
return 0;
}
M. Maze in Bolt
大力爆搜题，我们可以用\((r,d)\)来表示螺母位于第\(r\)行，且顺时针旋转了\(d\)个单位的状态，不难发现状态总数是\(O(RC)\)的，每次检验一个状态是否合法复杂度为\(O(C)\)
而转移的话就分上下移动和旋转来考虑即可，注意旋转的时候要考虑左右两个方向，并且在出现卡住的情况时要立即中止
当然这题还有个傻逼的地方就是初始时可以把螺母倒过来安装，因此需要reverse一遍后再跑一遍
总复杂度\(O(RC^2)\)
#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>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int n,m,vis[N][N],valid[N][N]; char s[N],a[N][N]; queue <pi> q;
inline int check(CI r,CI d)
{
if (~valid[r][d]) return valid[r][d];
for (RI i=0;i<m;++i) if (a[r][i]=='1'&&s[(i+d)%m]=='1') return valid[r][d]=0;
return valid[r][d]=1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%d%d%s",&n,&m,s),i=1;i<=n;++i) scanf("%s",a[i]);
memset(valid,-1,sizeof(valid)); memset(vis,0,sizeof(vis));
for (i=0;i<m;++i) if (check(1,i)) vis[1][i]=1,q.push(pi(1,i));
while (!q.empty())
{
int r=q.front().fi,d=q.front().se; q.pop();
if (r+1<=n&&check(r+1,d)&&!vis[r+1][d]) vis[r+1][d]=1,q.push(pi(r+1,d));
if (r-1>=1&&check(r-1,d)&&!vis[r-1][d]) vis[r-1][d]=1,q.push(pi(r-1,d));
for (j=(d+1)%m;j!=d;j=(j+1)%m)
{
if (!check(r,j)) break;
if (!vis[r][j]) vis[r][j]=1,q.push(pi(r,j));
}
for (j=(d-1+m)%m;j!=d;j=(j-1+m)%m)
{
if (!check(r,j)) break;
if (!vis[r][j]) vis[r][j]=1,q.push(pi(r,j));
}
}
for (i=0;i<m;++i) if (vis[n][i]) return puts("Y"),0;
reverse(s,s+m); memset(valid,-1,sizeof(valid)); memset(vis,0,sizeof(vis));
for (i=0;i<m;++i) if (check(1,i)) vis[1][i]=1,q.push(pi(1,i));
while (!q.empty())
{
int r=q.front().fi,d=q.front().se; q.pop();
if (r+1<=n&&check(r+1,d)&&!vis[r+1][d]) vis[r+1][d]=1,q.push(pi(r+1,d));
if (r-1>=1&&check(r-1,d)&&!vis[r-1][d]) vis[r-1][d]=1,q.push(pi(r-1,d));
for (j=(d+1)%m;j!=d;j=(j+1)%m)
{
if (!check(r,j)) break;
if (!vis[r][j]) vis[r][j]=1,q.push(pi(r,j));
}
for (j=(d-1+m)%m;j!=d;j=(j-1+m)%m)
{
if (!check(r,j)) break;
if (!vis[r][j]) vis[r][j]=1,q.push(pi(r,j));
}
}
for (i=0;i<m;++i) if (vis[n][i]) return puts("Y"),0;
return puts("N"),0;
}
Postscript
B题战俘闪总出列
- 2023 Programming ACM-ICPC American Regionalprogramming acm-icpc american regional 2023 programming acm-icpc american programming regional contest 2023 acm-icpc regional contest nanjing the universal acm-icpc regional acm-icpc regional contest seoul subregional programming acm-icpc contest 2022 programming collegiate acm-icpc 2021 programming collegiate acm-icpc programming shenyang regional contest