不写那么多没用的了
开题就发现 \(T4\) 原题， \(T1\) 大水题。
然后发现 \(T4\) 忘了。。。。
不扯了
打地鼠
大水题，我代码都不想放。。。
算了，还是放一下吧。。
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define sb(x) cout<<#x" = "<<x<<' '
#define jb(x) cout<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
#define scanf ak = scanf
int ak;
}
using namespace xin_io; static const int maxn = 2e3+10,inf = 1e9+7;
namespace xin
{
#define calc(x1,y1,x2,y2) (he[x2][y2] - he[x1-1][y2] - he[x2][y1-1] + he[x1-1][y1-1])
int he[maxn][maxn];
char s[maxn];
int n,k;
int maxx = -inf;
inline short main()
{
scanf("%d%d",&n,&k);
try(i,1,n)
{
scanf("%s",s+1);
try(j,1,n) he[i][j] = he[i-1][j] + he[i][j-1] - he[i-1][j-1] + (s[j] == '1');
}
if(k >= n) {cout<<he[n][n]<<endl; return 0;}
try(i,1,n - k + 1) try(j,1,n - k + 1)
// if(i + k - 1 <= n and j + k - 1 <= n)
{
maxx = std::max(maxx,calc(i,j,i+k-1,j+k-1));
}
cout<<maxx<<endl;
return 0;
}
}
signed main() {return xin::main();}
竞赛图
我们利用状态压缩枚举自己。
之后筛出来无效点。
预处理出来集合的交就行，
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define sb(x) cout<<#x" = "<<x<<' '
#define jb(x) cout<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
{
register type s = 0; register int f = 1; register char ch = gc();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this;
}}io;
}
using namespace xin_io; static const int maxn = 2e7+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
#define lowbit(i) (i & -i)
bool vis[maxn];
int lian[maxn];
int T,n,ans;
inline short main()
{
io >> T;
while(T--)
{
io >> n; ans = 0;
memset(vis,1,sizeof(bool) * (1 << n));
memset(lian,0,sizeof(int) * (1 << n));
try(i,1,n) try(j,1,n)
{
register int x; io >> x;
if(x) lian[1 << (i - 1)] |= (1 << (j - 1));
}
int ms = (1 << n) - 1;
lian[0] = ms;
try(s,1,ms)
{
register int low = lowbit(s);
lian[s] = (lian[low] & lian[low xor s]);
}
try(s,1,ms)
{
if(vis[s])
for(register int t=lian[s];t;t=((t-1)&lian[s]))
vis[s|t] = false;
}
try(i,0,ms) ans += vis[i];
cout<<ans<<endl;
}
return 0;
}
}
signed main() {return xin::main();}
糖果
还没做出来，先咕了。。。
树
这个似乎是今年 \(noi\) 原题，然后并且这道题目出的比 \(noi\) 要早很多。。。。
然后就是 \(noi\) 出了一道原题。。。。
恐怖如斯。
这个其实就可以树剖一下。
之后我们每次操作就是把路径上的所有点染成一种全新的颜色。
用线段树维护一个区间的边两端不同的点的数量就行。。
然而。。。。
其实打一个标记就能迅速写过。。。
只不过是因为数据水。
我就是这样过的
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define sb(x) cout<<#x" = "<<x<<' '
#define jb(x) cout<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
{
register type s = 0; register int f = 1; register char ch = gc();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
class xin_edge{public:int next,ver;}edge[maxn];
int head[maxn],zhi = 1;
inline void add(int x,int y) {edge[++zhi].ver = y; edge[zhi].next = head[x]; head[x] = zhi;}
int n,qnum;
int fa[maxn],dep[maxn],siz[maxn],hson[maxn],top[maxn],id[maxn],tot = 0;
void dfs1(int x,int f)
{
fa[x] = f; dep[x] = dep[f] + 1; siz[x] = 1;
for(register int i=head[x];i;i=edge[i].next)
{
register int y = edge[i].ver;
if(y == f) continue;
dfs1(y,x); siz[x] += siz[y];
if(siz[y] > siz[hson[x]]) hson[x] = y;
}
}
void dfs2(int x,int t)
{
top[x] = t;
if(hson[x]) dfs2(hson[x],t);
for(register int i=head[x];i;i=edge[i].next)
{
register int y = edge[i].ver;
if(y == fa[x] or y == hson[x]) continue;
dfs2(y,y);
}
}
inline int lca(int x,int y)
{
while(top[x] xor top[y])
{
if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) std::swap(x,y);
return x;
}
class xin_data
{
public:
int son1,son2;
xin_data(){}
xin_data(int x,int y):son1(x),son2(y){}
}d[maxn];
int val[maxn];
void update(int x,int y)
{
int allca = lca(x,y),pre_x = 0,pre_y = 0;
while(x xor allca)
{
val[x] = 0;
d[x] = xin_data(fa[x],pre_x);
pre_x = x;
x = fa[x];
}
while(y xor allca)
{
val[y] = 0;
d[y] = xin_data(fa[y],pre_y);
pre_y = y;
y = fa[y];
}
d[allca] = xin_data(pre_x,pre_y);
val[allca] = 1;
}
int query(int x,int y)
{
register int ret = 0,allca = lca(x,y);
while(x xor allca)
{
register int f = fa[x];
if((d[f].son1 or d[f].son2) and d[f].son1 != x and d[f].son2 != x) ret ++;
else ret += val[x];
x = f;
}
while(y xor allca)
{
register int f = fa[y];
if((d[f].son1 or d[f].son2) and d[f].son1 != y and d[f].son2 != y) ret ++;
else ret += val[y];
y = f;
}
return ret;
}
bool sp1 = 1;
class xin_seg
{
private:
#define ls(fa) (fa << 1)
#define rs(fa) (fa << 1 | 1)
inline void up(int fa) {t[fa].s = t[ls(fa)].s + t[rs(fa)].s;}
inline void down(int fa,int l,int r)
{
if(t[fa].debt == -1) return ;
t[ls(fa)].debt = t[rs(fa)].debt = t[fa].debt;
register int mid = l + r >> 1;
t[ls(fa)].s = t[fa].debt * (l - mid + 1); t[rs(fa)].s = t[fa].debt * (r - mid);
t[fa].debt = -1;
}
public:
class xin_tree{public:int s,debt;xin_tree():debt(-1){}}t[maxn];
void build(int fa,int l,int r)
{
if(l == r) return t[fa].s = 1,void();
register int mid = l + r >> 1;
build(ls(fa),l,mid); build(rs(fa),mid+1,r);
up(fa);
}
void update(int fa,int l,int r,int ql,int qr,int val)
{
if(ql <= l and qr >= r) {t[fa].s = val * (r - l + 1);t[fa].debt = val; return ;}
register int mid = l +r >> 1;
down(fa,l,r);
if(ql <= mid) update(ls(fa),l,mid,ql,qr,val);
if(qr > mid) update(rs(fa),mid+1,r,ql,qr,val);
up(fa);
}
int query(int fa,int l,int r,int ql,int qr)
{
if(ql <= l and qr >= r) return t[fa].s;
register int mid = l + r >> 1,ret = 0;
down(fa,l,r);
if(ql <= mid ) ret += query(ls(fa),l,mid,ql,qr);
if(qr > mid ) ret += query(rs(fa),mid+1,r,ql,qr);
return ret;
}
}t;
inline short main()
{
io >> n;
try(i,1,n-1)
{
register int x,y; io >> x >> y;
add(x,y); add(y,x);
if((x != y - 1) and (x != y + 1)) sp1 = 0;
val[i+1] = 1;
}
dfs1(1,0); dfs2(1,1);
if(sp1)
{
t.build(1,1,n);
io >> qnum;
try(que,1,qnum)
{
register int op,x,y; io >> op >> x >> y;
if(y < x) std::swap(x,y);
if(op == 1)
{
t.update(1,1,n,x + 1,y,0);
t.update(1,1,n,x,x,1);
t.update(1,1,n,y+1,y+1,1);
}
else
printf("%d\n",t.query(1,1,n,x+1,y));
}
return 0;
}
io >> qnum;
try(que,1,qnum)
{
register int op; io >> op;
if(op == 1)
{
register int x,y; io >> x >> y;
update(x,y);
}
else
{
register int x,y; io >> x >> y;
printf("%d\n",query(x,y));
}
}
return 0;
}
}
signed main() {return xin::main();}