noip前准备日记
csp就把它埋了吧。
Day -26
刚考完csp，没有考试。。
刷了几个好题。。
P3076 [USACO13FEB] TaxiG
这个题目硬想是不好想的，但是我们可以分步来做。
首先我们知道每个 \(s_i\) 到 \(t_i\) 的距离一定是一定的。
我们没有办法避免，所以就要先加上这个东西。
之后我们就要送完每个奶牛之后去接下一个。
这个东西是我们需要仔细想的。
每一个奶牛的行程还是相当一条线段，我们现在的主要任务就是将这些线段用最小的代价收尾相接起来。
那么我们就可以将每一个起点的坐标进行排序，然后将每一个终点的坐标进行排序，之后按位相减的一定就是代价最小的答案。
可是这样的话就少掉了终点和起点的路程。
因为我们从起点出发一定会先去找到一个起点去接奶牛，终点之前也一定是一个终点才对。
所以我们就可以把终点塞到起点的排序的数组中，把起点塞到终点的，然后再去排序。
按位相减就能得到最优的答案了。
那么这个结论如何证明呢？？
我们如果都进行排序之后，如果任意交换一对数值，那么得到的代价一定会变大。
所以排序后的就一定是最小的。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next.y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10;
#define int long long
namespace xin
{
int s[maxn],t[maxn];
int n,m,ans;
inline short main()
{
io >> n >> m;
try(i,1,n) io >> s[i] >> t[i],ans += abs(s[i] - t[i]);
s[n+1] = m; t[n+1] = 0;
std::sort(s+1,s+n+2); std::sort(t+1,t+n+2);
try(i,1,n+1) ans += abs(s[i] - t[i]);
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
[NOIP2018 提高组] 赛道修建
首先这个题目问的最大的最小值就能一眼看出来这就是一个二分答案。
那么我们该如何进行check就是问题所在了。
我们首先一定是想要让赛道的数量是尽可能多的。
所以我们如果首先选择离根节点比较近的节点，那么就会损失掉更多的赛道。
所以我们首先递归到最下面开始贪心。
现在就有一个问题，就是我们手上有一个序列，然后我们需要找到最小的值使得两个不同的数 \(x\)，\(y\)使得 \(x+y\ge val\)，之前考到过一个 meet in middle的题目自己当时并不知道该如何在小于 \(\mathcal O(n^2)\) 的复杂度下求出这个东西。
然后就学到了二分可以做到，所以我们在一个序列上面进行二分。
但是我们需要判断重复，如果重复，那么将指针加一一定是最优的选择。
之后我们对于没有被选到的边进行传递，显然只能传递一个，那么最大的一定就是最优的情况。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10;
#define int long long
namespace xin
{
class xin_edge{public:int next,ver,w;}edge[maxn];
int head[maxn],rp;
inline void add(int x,int y,int z) {edge[++rp].ver = y; edge[rp].next = head[x]; edge[rp].w = z; head[x] = rp;};
int n,m,he = 0,ret;
int pre[maxn],temp[maxn],zhi = 0,vis[maxn];
void dfs(int x,int fa,int val)
{
// jb(x);
go(i,x) if(y != fa) dfs(y,x,val);
zhi = 0;
go(i,x) if(y != fa) temp[++zhi] = pre[y] + edge[i].w;
std::sort(temp+1,temp+zhi+1);
// jb(x);
// try(i,1,zhi) cout<<temp[i]<<' ';
// cout<<endl;
while(temp[zhi] >= val) ret --,zhi --;
// jb(ret);
try(i,1,zhi) if(vis[i] != x)
{
int pos = std::lower_bound(temp+1,temp+zhi+1,val - temp[i]) - temp;
// sb(i);sb(val - temp[i]);jb(pos);
while(pos <= zhi and (vis[pos] == x or pos == i)) pos ++;
// jb(pos);
if(pos <= zhi) vis[pos] = vis[i] = x,ret --;
}
throw(i,zhi,1) if(vis[i] != x) {pre[x] = temp[i]; break;}
}
inline int check(int x)
{
memset(vis,0,sizeof(int) * (n + 1));
memset(pre,0,sizeof(int) * (n + 1));
ret = m;
dfs(1,0,x);
return ret <= 0;
}
inline short main()
{
io >> n >> m;
try(i,1,n-1)
{
register int x,y,z; io >> x >> y >> z;
add(x,y,z); add(y,x,z); he += z;
}
// go(i,1) jb(y);
int l = 0,r = he,ans = 0;
// jb(r);
// cout<<check(7987)<<endl;
// return 0;
while(l <= r)
{
register int mid = l + r >> 1;
if(!check(mid)) r = mid - 1;
else l = mid + 1,ans = mid;
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
[CSP-S 2021] 廊桥分配
纪念一下爆炸的csp吧。
思路是对的，但是确实实现假掉了，最后20min什么其实也救不回来，顶多就是一个文件名什么的。
首先我们一定会有一个 \(40pts\) 的 \(\mathcal O(n^2log)\) 的做法。
然后我删了
就是对于每一种分配方式然后 \(\mathcal O(nlog)\) 进行 \(check\)
但是呢，这个不够优秀。
所以我们考虑如何优化 \(check\)。
我们其实可以挨个考虑贡献，我们首先进行一遍预处理。
也其实就是模拟这个过程一遍，然后我们就可以发现在当时有 \(x\) 个廊桥被占有的时候，就会对 \(x\)~\(n\) 的答案造成 \(1\) 的贡献。
那么这其实就可以使用树状数组来维护。
那么如何预处理呢。
这就是我考场上没掉的地方，就是一个顺序的问题。
因为粗心，考场上并没有看到这个东西每一个坐标都是独一无二的。
然后就直接在优先队列里面按照 \(r\) 排序了。
其实这样并不是对的，一般的数据都会把我杀死，但是infoj给了我30
所以其实离散化一下每一个位置只有一个变化，这样使用一个普通的小跟堆就好了。
也确实，当时想要搏一把，20min属实啥也调不对。
但是没有打组合拳属实不应该啊。
菜就是菜了。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next.y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10;
namespace xin
{
int n,m1,m2;
class xin_bit
{
private:
#define low(x) (x & -x)
public:
int c[maxn];
inline void add(int x,int val) {for(;x<=n;x+=low(x)) c[x] += val;}
inline int query(int x) {int ret = 0; for(;x;x-=low(x)) ret += c[x]; return ret;}
}bit1,bit2;
class xin_data
{
public:
int l,r;
xin_data(){}
xin_data(int l,int r):l(l),r(r){}
}d1[maxn],d2[maxn];
int lisan1[maxn],cnt1 = 0,cnt2 = 0;
int lisan2[maxn];
xin_data pos1[maxn],pos2[maxn];
std::priority_queue<int,std::vector<int>,std::greater<int>>q1,q2;
int vis1[maxn],vis2[maxn];
inline short main()
{
io >> n >> m1 >> m2;
try(i,1,m1) io >> d1[i].l >> d1[i].r,lisan1[++cnt1] = d1[i].l,lisan1[++cnt1] = d1[i].r,q1.push(i);
try(i,1,m2) io >> d2[i].l >> d2[i].r,lisan2[++cnt2] = d2[i].l,lisan2[++cnt2] = d2[i].r,q2.push(i);
std::sort(lisan1+1,lisan1+cnt1+1); std::sort(lisan2+1,lisan2+cnt2+1);
try(i,1,m1)
{
d1[i].l = std::lower_bound(lisan1+1,lisan1+cnt1+1,d1[i].l) - lisan1;
d1[i].r = std::lower_bound(lisan1+1,lisan1+cnt1+1,d1[i].r) - lisan1;
pos1[d1[i].l] = xin_data(i,0); pos1[d1[i].r] = xin_data(i,1);
}
try(i,1,m2)
{
d2[i].l = std::lower_bound(lisan2+1,lisan2+cnt2+1,d2[i].l) - lisan2;
d2[i].r = std::lower_bound(lisan2+1,lisan2+cnt2+1,d2[i].r) - lisan2;
pos2[d2[i].l] = xin_data(i,0); pos2[d2[i].r] = xin_data(i,1);
}
// try(i,1,m1) sb(d1[i].l),jb(d1[i].r);
try(i,1,2*m1)
{
if(pos1[i].r == 0) vis1[pos1[i].l] = q1.top(),bit1.add(q1.top(),1),q1.pop();
else q1.push(vis1[pos1[i].l]);//,jb(vis1[pos1[i].l]);
}
try(i,1,2*m2)
{
if(pos2[i].r == 0) vis2[pos2[i].l] = q2.top(),bit2.add(q2.top(),1),q2.pop();
else q2.push(vis2[pos2[i].l]);
}
int ans = 0;
try(i,0,n)
ans = std::max(ans,bit1.query(i) + bit2.query(n-i));
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
[NOIP2014 提高组] 联合权值
似乎感觉在哪里做过啊。
然后发现确实做过，然后那个是一个改编的题目。
暴力的思路比较一样，但是实际上正解并不是一样的。
这个题目首先暴力应该是最差应该只有 \(30pts\)，但是没想到当时 \(CCF\) 的数据那么友善，一直猛给部分分数。
然后我就有 \(70pts\)，然后开始考虑正解。
因为我们考虑的是距离为 \(2\) 的，所以一定会有一个中专的点。
但是问题就是知道这个点了怎么做?
考虑最最朴素的算法，也就是暴力算，式子就是：
\[2(a_1*a_2+a_1*a_3+...+a_{n-1} * a_n) \]那么其实就是
\[(\sum a)^2-\sum a^2 \]所以就可以很快算出来了。
至于最大值，那么其实就是每一个中转点连接的最大值和次大值的乘积。
之后我总感觉这个的时间复杂度不是很对，但是似乎跑的飞快。。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10;
#define int long long
namespace xin
{
const int mod = 10007;
std::vector<int>vec[maxn/5];
int n;
int w[maxn];
int ans1,ans2;
inline short main()
{
io >> n;
try(i,1,n-1)
{
register int x,y; io >> x >> y;
vec[x].push_back(y); vec[y].push_back(x);
}
try(i,1,n) io >> w[i];
try(i,1,n)
{
int he1 = 0,he2 = 0;
int maxx1 = 0,maxx2 = 0;
for(auto y : vec[i])
{
if(w[y] > maxx1) maxx2 = maxx1,maxx1 = w[y];
else if(w[y] > maxx2) maxx2 = w[y];
he1 += w[y];
(he2 += w[y] * w[y]) %= mod;
}
he1 = he1 * he1 % mod;
ans1 = std::max(ans1,maxx1 * maxx2);
(ans2 += he1 - he2 + mod) %= mod;
}
cout<<ans1<<' '<<ans2<<endl;
return 0;
}
}
signed main() {return xin::main();}
CF702C Cellular Network
就是一个大大大大水题。
然后看错题目然后调了半天。
生气。
就是计算每一个的前驱后继，然后取最小值的最大值就行了。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10;
//#define int long long
namespace xin
{
int n,m,ans;
int a[maxn],b[maxn],pi[maxn];
int pai1[maxn],pai2[maxn];
int pos1[maxn],pos2[maxn];
int ner1[maxn],ner2[maxn];
bool vis[maxn];
inline short main()
{
io >> n >> m;
try(i,1,n) io >> a[i]; try(i,1,m) io >> b[i],pai1[i] = pai2[i] = b[i],pai2[i] = -pai2[i];//,jb(pai2[i]);
std::sort(pai1+1,pai1+m+1); std::sort(pai2+1,pai2+m+1);
// jb(std::lower_bound(pai2+1,pai2+m+1,-17) - pai2);
// try(i,1,m) sb(pai1[i]),jb(pai2[i]);
try(i,1,n)
{
pos1[i] = std::lower_bound(pai1+1,pai1+m+1,a[i]) - pai1,pos2[i] = std::lower_bound(pai2+1,pai2+m+1,-a[i]) - pai2;
pos2[i] = m - pos2[i] + 1;
if(!pos1[i] or pos1[i] == m + 1) ans = std::max(ans,abs(a[i] - pai1[pos2[i]]));
else if(!pos2[i] or pos2[i] == m + 1) ans = std::max(ans,abs(a[i] - pai1[pos1[i]]));
else ans = std::max(ans,std::min(abs(a[i] - pai1[pos1[i]]),abs(a[i] - pai1[pos2[i]])));
// sb(pos1[i]); sb(pos2[i]); jb(ans);
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
Day -25
今天又开始联考了。
开始感觉上来是一个很普通的大水题。。
然后认为线段树直接就是可以过掉这个题目。
然后发现范围。。。
\[n\leq5*10^6 \]淦。
然后开始疯狂想如何 \(\mathcal O(n)\) 做。
发现是一堆的线段，然后认为可以差分，然而似乎并不知道该如何差分。
但是脑袋当中就一直出现带着 \(log\) 的做法。
感觉似乎只有 \(60pts\)，鉴于csp的经验，因为时间比较充足，所以打上了对拍
在打 pai.cpp的时候，突然发现似乎这个暴力的复杂度是均摊一个 \(n\) 的，然后试着证明了一下，发现确实。
然后就反过来了，用着自己的线段树拍着暴力，发现暴力跑极限只有
\(0.7s\)，感觉很好。
开 \(T2\) ，发现手头没有小于 \(\mathcal O(n^3)\) 的做法，感觉不是很好。。
然后就写了一个 \(\mathcal O(n^3)\) 的，然后写了一个菊花图的部分分数。
但是如果只要我找到 \(\mathcal O(n^2log)\) 的做法，那么我就可以解决掉链的部分和一个询问的部分。
这样就有足足 \(80pts\)，然而失败了。
\(T3\) 和 \(T4\) 都是写了一个极端弱智的部分分数走人了。
然后就是 \(100+45+25+10\)
树上的数
这个名字似乎像是一个原题，但是完全不是。
做法很简单，但是不太容易想到去证明这个玩意的复杂度。
并且极端卡常。
我也不知道为啥我这么快
直接每一个询问进行 \(dfs\)，遇到已经贡献过的就停下来就好了。
只有 \(n\) 个节点，所以一定就是 \(\mathcal O(n)\) 的。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for( int i=a;i<=b;++i)
#define throw(i,a,b) for( int i=a;i>=b;--i)
#define go(i,x) for( signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 5e6+10,inf = 1e9+10;
// #define int long long
namespace xin
{
int n,m;
class xin_edge{public:int next,ver;}edge[maxn];
int head[maxn],rp;
auto add = [](int x,int y){edge[++rp].ver = y; edge[rp].next = head[x]; head[x] = rp;};
int fa[maxn];
int a,b,he;
int q[maxn],tot,id[maxn],siz[maxn];
bool vis[maxn];
void run(int x)
{
if(!vis[x]) return ;
he += vis[x]; vis[x] = 0;
go(i,x) run(y);
}
inline short main()
{
file(tree);
io >> n >> m;
io >> a >> b;
fa[2] = 1; add(1,2); vis[1] = vis[2] = 1;
try(i,3,n) fa[i] = ((1ll * fa[i - 1] * a + b) ^ 19760817) % (i - 1) + 1,add(fa[i],i),vis[i] = 1;
io >> q[1] >> a >> b;
int ans;
run(q[1]);
ans = n - he;
// sb(siz[q[1]]); jb(he);
try(i,2,m)
{
q[i] = 1ll * (((1ll * q[i - 1] * a + b) ^ 19760817) ^ (i << 1)) % (n - 1) + 2;
run(q[i]);
ans ^= n - he;
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
时代的眼泪
其实这个题目的突破就是 \(\mathcal O(n)\) 的做法。
我们现将权值进行离散化，之后建立权值树状数组。
我们先从 \(1\) 节点开始 \(dfs\)，之后到达一个节点就变成一个节点的状态，回溯就好了。
具体就是到达一个节点，然后就将 \(1\) ~ \(w_x-1\) 的下标增加一个 \(1\)。
这就是对下面的点的贡献。
这样就能 \(nlog\) 求出来一个的了。
然后的关键就是在换根 \(dp\) 上面，我们有一个之后，其他的答案自然就很好从那个来转移了。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+10;
#define int long long
namespace xin
{
class xin_edge{public:int next,ver,w;}edge[maxn];
int head[maxn],rp;
inline void add(int x,int y) {edge[++rp].ver = y; edge[rp].next = head[x]; head[x] = rp;}
int n,qnum,w[maxn];
class xin_bit
{
private:
#define low(x) (x & -x)
public:
int c[maxn];
inline void add(int x,int val) {for(;x<=n;x+=low(x)) c[x] += val;}
inline int query(int x) {int ret = 0; for(;x;x-=low(x)) ret += c[x]; return ret;}
}bit;
int lisan[maxn],cnt = 0;
int ret;
int f[maxn],dp[maxn];
void dfs(int x,int fa)
{
bit.add(w[x],1);
int temp = bit.query(w[x]-1),pre = temp;
go(i,x) if(y != fa)
{
dfs(y,x);
int now = bit.query(w[x]-1);
edge[i].w = now - pre; pre = now;
}
f[x] = bit.query(w[x]-1) - temp;
dp[1] += f[x];
// bit.add(w[x]-1,-1);
}
void get_ans(int x,int fa)
{
go(i,x) if(y != fa)
{
dp[y] = dp[x] - edge[i].w + bit.query(w[y]-1) - f[y];
get_ans(y,x);
}
}
inline short main()
{
file(tears);
io >> n >> qnum;
try(i,1,n) io >> w[i],lisan[++cnt] = w[i];
std::sort(lisan+1,lisan+cnt+1);
int k = std::unique(lisan+1,lisan+cnt+1) - (lisan + 1);
try(i,1,n) w[i] = std::lower_bound(lisan+1,lisan+k+1,w[i]) - lisan;
try(i,1,n-1)
{
register int x,y; io >> x >> y;
add(x,y); add(y,x);
}
dfs(1,0);
get_ans(1,0);
try(i,1,qnum)
{
register int x; io >> x;
printf("%lld\n",dp[x]);
}
return 0;
}
}
signed main() {return xin::main();}
传统艺能
本质不同的子序列的个数的这个东西还是没有记住啊。
\[f_c = \sum_{char \in \text{字符集}}f_{char} + 1 \]意义就是对于每一个以 \(c\) 结尾的子序列的个数为 \(f_c\)，然后这个东西就是表示在每一种字符结尾后面再去接一个新的字符，之后在加上自己一个的新字符就是所有的情况了。
所以这个玩意可以矩阵快速幂
设置三个矩阵，然后修改在线段树上面修改，注意矩阵不满足交换律。
| 1 | |||
|---|---|---|---|
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 |
| 1 | 1 | ||
|---|---|---|---|
| 1 | |||
| 1 | 1 | ||
| 1 | 1 |
| 1 | 1 | ||
|---|---|---|---|
| 1 | 1 | ||
| 1 | |||
| 1 |
之后向量的 a[1][1] + a[1][2] + a[1][3]就是答案了。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gec() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define gc() getchar()
#define debug std::cerr<<"debug"<<endl
#define scnaf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10;
#define int long long
namespace xin
{
const int mod = 998244353;
char s[maxn],in[10];
int a[maxn],f[maxn];
bool sp = 1;
class xin_mat
{
public:
int a[5][5];
xin_mat(){}
inline void out()
{
try(i,1,4)
{
try(j,1,4)
cout<<a[i][j]<<' ';
cout<<endl;
}
cout<<endl;
}
// xin_mat(int n,int m):n(n),m(m){}
friend xin_mat operator * (const xin_mat &x,const xin_mat &y)
{
xin_mat ret;
// x.out(); y.out();
// try(i,1,4)
// {
// try(j,1,4)
// cout<<x.a[i][j]<<' ';
// cout<<endl;
// }
// try(i,1,4)
// {
// try(j,1,4)
// cout<<y.a[i][j]<<' ';
// cout<<endl;
// }
memset(ret.a,0,sizeof(ret.a));
try(i,1,4) try(j,1,4) try(k,1,4)
(ret.a[i][j] += x.a[i][k] * y.a[k][j]) %= mod;
// jb(ret.a[1][1]);
// try(i,1,4)
// {
// try(j,1,4)
// cout<<ret.a[i][j]<<' ';
// cout<<endl;
// }
return ret;
}
}base,ch[5],vec;
int n,m;
class xin_seg
{
private:
#define ls(fa) (fa << 1)
#define rs(fa) (fa << 1 | 1)
#define up(fa) (t[fa].s = t[ls(fa)].s * t[rs(fa)].s)
public:
class xin_tree{public:xin_mat s;}t[maxn];
void build(int fa,int l,int r)
{
if(l == r) return t[fa].s = ch[a[l]],void();
register int mid = l + r >> 1;
build(ls(fa),l,mid); build(rs(fa),mid+1,r);
up(fa);
// t[fa].s.out();
}
void upd(int fa,int l,int r,int pos,int val)
{
if(l == r) return t[fa].s = ch[val],void();
register int mid = l + r >> 1;
if(pos <= mid) upd(ls(fa),l,mid,pos,val);
else upd(rs(fa),mid+1,r,pos,val);
up(fa);
}
xin_mat 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,ok = 0; xin_mat ret;
if(ql <= mid) ret = query(ls(fa),l,mid,ql,qr),ok = 1;
if(qr > mid)
{
if(ok) ret = ret * query(rs(fa),mid+1,r,ql,qr);
else ret = query(rs(fa),mid+1,r,ql,qr);
}
return ret;
}
}t;
inline void init()
{
try(i,1,3) memset(ch[i].a,0,sizeof(ch[i].a));
// ch[1] = ch[2] = ch[3] = xin_mat(4,4);
ch[1].a[1][1] = ch[1].a[2][1] = ch[1].a[3][1] = ch[1].a[4][1] = ch[1].a[2][2] = ch[1].a[3][3] = ch[1].a[4][4] = 1;
ch[2].a[1][1] = ch[2].a[1][2] = ch[2].a[2][2] = ch[2].a[3][2] = ch[2].a[3][3] = ch[2].a[4][2] = ch[2].a[4][4] = 1;
ch[3].a[1][1] = ch[3].a[2][2] = ch[3].a[3][3] = ch[3].a[4][4] = ch[3].a[1][3] = ch[3].a[2][3] = ch[3].a[4][3] = 1;
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(string);
#endif
io >> n >> m;
scanf("%s",s+1);
try(i,1,n)
{
a[i] = s[i] - 'A' + 1;
if(a[i] != 1) sp = 0;
}
memset(base.a,0,sizeof(base.a)); memset(vec.a,0,sizeof(vec.a));
try(i,1,4) base.a[i][i] = 1;
vec.a[1][4] = 1;
init();
// try(cse,1,3)
// {
// try(i,1,4)
// {
// try(j,1,4)
// cout<<ch[cse].a[i][j]<<' ';
// cout<<endl;
// }
// cout<<endl;
// }
t.build(1,1,n);
try(cse,1,m)
{
register int op; io >> op;
if(op == 1)
{
register int x; io >> x;
char in[10]; scanf("%s",in+1);
a[x] = in[1] - 'A' + 1;
t.upd(1,1,n,x,a[x]);
}
else
{
register int l,r; io >> l >> r;
xin_mat ret = t.query(1,1,n,l,r),temp = vec;
temp = temp * ret;
printf("%lld\n",(temp.a[1][1] + temp.a[1][2] + temp.a[1][3]) % mod);
}
}
return 0;
}
}
signed main() {return xin::main();}
铺设道路
贪心。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10;
#define int long long
namespace xin
{
const int mod = 1e9+7;
std::queue<int>q;
std::stack<int>st;
int n,a[maxn],b[maxn];
int ans1,ans2,ans;
inline short main()
{
#ifdef ONLINE_JUDGE
file(road);
#endif
io >> n;
try(i,1,n) io >> a[i];
try(i,1,n+1) b[i] = a[i] - a[i-1],ans += (b[i] > 0) ? b[i] : 0;
try(i,1,n+1)
{
if(b[i] > 0) q.push(i);
else
{
while(b[i] < 0)
{
register int x = q.front();
if(abs(b[x]) <= abs(b[i]))
{
b[i] += b[x];
ans1 = (ans1 + (i - x) * (i - x) % mod * b[x] % mod) % mod;
q.pop();
}
else
{
b[x] += b[i];
ans1 = (ans1 + (i - x) * (i - x) % mod * (-b[i]) % mod) % mod;
b[i] = 0;
}
}
}
}
try(i,1,n+1) b[i] = a[i] - a[i-1];
try(i,1,n+1)
{
if(b[i] > 0) st.push(i);
else
{
while(b[i] < 0)
{
register int x = st.top();
if(abs(b[x]) < abs(b[i]))
{
b[i] += b[x];
ans2 = (ans2 + (i - x) * (i - x) % mod * b[x] % mod) % mod;
st.pop();
}
else
{
b[x] += b[i];
ans2 = (ans2 + (i - x) * (i - x) % mod * (-b[i]) % mod) % mod;
b[i] = 0;
}
}
}
}
cout<<ans<<endl<<ans2<<endl<<ans1<<endl;
return 0;
}
}
signed main() {return xin::main();}
Day -24
昨天在做 \(T2\) 的时候，发现自己的树状数组的理解是偏差的。
所以就重新学了一遍树状数组，发现其实树状数组的基本是单点修改，区间查询
我一直认为是区间修改，单点查询啊。。
只不过区间修改可以使用差分来解决。
树状数组还有一个强大的用处，就是进行区间修改，区间查询
感觉很强，实际更强。
无论是空间上面还是时间上面又要优过线段树。
这个其实也是一个差分的过程。
\[\sum a_i = \sum \sum d_i\\ \sum_{i=1}^{p} = (p+1)\sum d_i - \sum_{i=1}^{p}d_i * i \]所以就可以维护两个差分的数组，然后在查询的时候(p + 1) * c1[i] - c2[i]就好了。
code
class xin_bit
{
private:
#define low(x) (x & -x)
public:
int c1[maxn],c2[maxn];
inline void add(int x,int val)
{
for(int i=x;i<=n;i+=low(i)) c1[i] += val,c2[i] += x * val;
}
inline void upd(int l,int r,int val) {add(l,val); add(r+1,-val);}
inline int ask(int x)
{
int ret = 0;
for(int i=x;i;i-=low(i))
ret += (x + 1) * c1[i] - c2[i];
return ret;
}
inline int query(int l,int r) {return ask(r) - ask(l-1);}
}bit;
还是很快的。
然后开始考试啊。
几天的考试颇有几番不顺利。
上来的思路感觉修正很对，然后飞速写完，一下子过了小样例。
然后测大样例。。。
发现两百个里面有两个是不一样的，心态稍炸。
然后疯狂调试，发现做法是假的，但是认为 \(q=1\) 的点是可以过去的。
所以就放下了。
然后开始做 \(T2\)，然后认为很垃圾的一个题目。
然后。。。
小样例又过了。
大样例。。。还是错两个？？！！
然后又没了。
最后两个题目的 \(pretask\) 都没有过掉。。。
然后后面两个题目的东西的暴力疯狂挼了一下。
然后。。。\(30+20+20=70\)
垃圾分数。
宝藏
首先我们要分析出一个很妙的性质，就是说这个的答案是随 \(x\) 的增大而减小的。
那么就可以二分出来答案。
提前两种的排序，然后就是 \(qnlogn\) 的复杂度
如果仔细的话，你会发现这个子任务 \(2\) 并没有给 \(Q\) 的范围。
是不是他忘了呢？？？
不是，这个真的就是 \(3*10^5\)
所以这个东西只有 \(50pts\) 。
我们考虑正解，我们回想自己在 \(check\) 的过程中，我们分开左边和右边。
我们会分别对左右进行排序。
那么我们不妨把每一种答案都预处理出来，因为对于相邻的询问，变化还是比较小的。
所以两边就可以维护一个 \(set\)，之后就可以 \(log\) 转移。
然后我才知道平常一直不让用的关键字next这个函数的用法
我们维护 \(ls,rs,mid1,mid2\) 分别表示左边的时间和，右边的时间和，还有左边中间的，右边中间的。
之后就能转移到我们想要的答案了。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10; const ll llinf = 1e18+10;
#define int long long
namespace xin
{
class xin_data
{
private:
friend bool operator < (xin_data x,xin_data y)
{
if(x.tim xor y.tim) return x.tim < y.tim;
return x.id < y.id;
}
friend bool operator <= (xin_data x,xin_data y)
{
if(x.tim xor y.tim) return x.tim < y.tim;
return x.id <= y.id;
}
public:
int val,tim,id;
xin_data(){}
xin_data(int val,int tim,int id):val(val),tim(tim),id(id){}
}d[maxn];
int n,qnum,t;
std::set<xin_data>s1,s2;
xin_data mid1,mid2;
int ans[maxn];
inline short main()
{
#ifdef ONLINE_JUDGE
file(treasure);
#endif
io >> n >> t >> qnum;
try(i,1,n) io >> d[i].val >> d[i].tim,d[i].id = i;
std::sort(d+1,d+n+1,[](xin_data x,xin_data y){return (x.val == y.val) ? x.id < y.id : x.val < y.val;});
try(i,1,n-1) s1.insert(d[i]);
s1.insert(mid1); s2.insert(mid2);
int ls = 0,rs = 0,zhi = n;
bool ok = 0;
for(int i=1;i<=n;i+=2)
{
if(ok) {ans[i] = -1; continue;}
while(ls + rs + d[zhi].tim > t and zhi)
{
s2.insert(d[zhi]);
auto it = s2.find(mid2);
if(d[zhi] <= mid2) rs += d[zhi].tim - mid2.tim,mid2 = *--it;
zhi --;
it = s1.find(mid1);
if(d[zhi] <= mid1)
{
if(++it != s1.end()) mid1 = *it;
else {ok = 1; break;}
ls += mid1.tim - d[zhi].tim;
}
s1.erase(d[zhi]);
}
ans[i] = d[zhi].val;
if(ok) {ans[i] = -1; continue;}
auto it = s2.find(mid2);
if(++it == s2.end())
{
s2.insert(d[zhi]);
auto it = s2.find(mid2);
if(d[zhi] <= mid2) rs += d[zhi].tim - mid2.tim,mid2 = *--it;
zhi --;
it = s1.find(mid1);
if(d[zhi] <= mid1)
{
if(++it != s1.end()) mid1 = *it;
else {ok = 1; break;}
ls += mid1.tim - d[zhi].tim;
}
s1.erase(d[zhi]);
}
it = s2.find(mid2); mid2 = *next(it),rs += mid2.tim;
it = s1.find(mid1); if(next(it) != s1.end()) mid1 = *next(it),ls += mid1.tim; else ok = 1;
}
try(cse,1,qnum)
{
register int x; io >> x;
printf("%lld\n",ans[x]);
}
return 0;
}
}
signed main() {return xin::main();}
寻找道路
考场上面想到了正解，但是因为细节没有调出来。。。
这个题目实际上就是一个广搜，是一个分布广搜这个是我自己起的名字。。。
然后注意 \(0\) 和 \(1\) 的转移顺序，这样的话队列的第一个一定就是最优的答案。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+10; const ll llinf = 1e18+10;
#define int long long
namespace xin
{
const int mod = 1e9+7;
class xin_edge{public:int next,ver,w;}edge[maxn];
int head[maxn],rp;
inline void add(int x,int y,int z){edge[++rp].ver = y; edge[rp].next = head[x];edge[rp].w = z; head[x] = rp;}
int n,m;
bool vis[maxn];
int a[maxn],b[maxn];
std::vector<int>ans[maxn/10],vec;
class xin_data
{
public:
int x,tim;
xin_data(){}
xin_data(int x,int tim):x(x),tim(tim){}
};
int dis[maxn],d[maxn];
std::queue<int>q;
void dfs(int x)
{
vis[x] = 1; q.push(x); dis[x] = 0;
go(i,x) if(!vis[y] and !edge[i].w) dfs(y);
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(path);
#endif
io >> n >> m;
try(i,1,m)
{
register int x,y,z; io >> x >> y >> z;
add(x,y,z);
}
memset(dis,-1,sizeof(int) * (n + 1));
dfs(1);
// debug;
int now1,now2;
while(q.size())
{
int zhi = 0; now1 = d[q.front()]; now2 = dis[q.front()];
while(q.size() and d[q.front()] == now1 and dis[q.front()] == now2) a[++zhi] = q.front(),q.pop();
try(i,1,zhi)
{
int x = a[i];
go(i,x) if(!vis[y] and !edge[i].w)
{
d[y] = d[x] + 1;
dis[y] = dis[x] * 2 % mod;
q.push(y); vis[y] = 1;
}
}
try(i,1,zhi)
{
int x = a[i];
go(i,x) if(!vis[y] and edge[i].w)
{
d[y] = d[x] + 1;
dis[y] = (dis[x] * 2 + 1) % mod;
q.push(y); vis[y] = 1;
}
}
}
try(i,2,n) printf("%lld ",dis[i]);
return 0;
}
}
signed main() {return xin::main();}
考试总结
这场考试实际上做的很差，在时间分配问题上还有很大的问题，主要在第一个题目上面的用时其实还是不够，总是感觉会影响后面的题目，但是其实只有第一个题目和第二个题目是比较可做的。
其实应该敢用时间在读题目上面，可以开始的时候先把左右的题目通读一遍，之后可以根据估计的难度进行时间的分配，可以先把认为非常不可做的题目的暴力打完，这样心里面就没有了负担。
之后再去花费比较大量的时间在自己有可能做出来的题目上面。
这样就能将自己会做的题目尽可能的拿上最多的分数了。
Day -23
今天刚上来就有一个口胡比赛，结果一番口胡正解。。。
红黑树
首先这个每一次的操作永远是以颜色相同的联通块为前提的。
所以我们看这个树的最小单位就应该是一个一个的联通块。
那么就可以开始缩点，把颜色相同的联通块缩成一个点。
之后考虑如何将这个树以最小的操作数量变成一个颜色。
现在的树上的节点每一个都是互不相同的，也就是每隔一个一种颜色。
假设现在是一个这样的树（缩点之后的树），那么这个树的最长的链就是 \(15...1...3...........9...10\) 这个链。
假设我们首先没有操作这个直径上面的节点。
那么直径上面一定还会留下没有被操作过的节点需要被操作。
这样的操作数量一定不会比直径的长度的二分之一要小。
如果我们直接对于直径每隔一个节点进行操作。
那么因为直径无论在哪一个节点后面都是不短的，那么其他所有的子树一定也会在直径操作结束之前被操作完成。
所以答案一定也就是(直径+1)/2
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define debug std::cerr<<"debug"<<endl
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10;
namespace xin
{
class xin_edge{public:int next,ver;}edge[maxn];
int head[maxn],zhi;
inline void add(int x,int y) {edge[++zhi].ver = y ;edge[zhi].next= head[x]; head[x] = zhi;}
class xin_data{public:int x,y;}d[maxn];
class xin_tim
{
public:
int x,tim;
xin_tim(){}
xin_tim(int x,int tim):x(x),tim(tim){}
};
int a[maxn],n;
int fa[maxn];
int biao[maxn],tot;
bool vis[maxn];
inline int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
void dfs(int x,int f)
{
go(i,x) if(y != f)
{
dfs(y,x);
if(a[y] == a[x]) fa[find(x)] = find(y);
}
}
inline short main()
{
io >> n;
try(i,1,n) io >> a[i],fa[i] = i;
try(i,1,n-1)
{
io >> d[i].x >> d[i].y;
// add(x,y); add(y,x);
add(d[i].x,d[i].y); add(d[i].y,d[i].x);
}
dfs(1,0);
// try(i,1,n) sb(i),jb(find(i));
try(i,1,n)
{
int fx = find(i);
if(!vis[fx])
{
vis[fx] = 1;
biao[fx] = ++tot;
}
}
// try(i,1,n) sb(i),jb(biao[find(i)]);
memset(head,0,sizeof(int) * (n + 1)); zhi = 0;
try(i,1,n-1)
{
int fx = find(d[i].x),fy = find(d[i].y);
if(fx xor fy) add(biao[fx],biao[fy]),add(biao[fy],biao[fx]);//,cout<<(biao[fy])<<' '<<(biao[fx])<<endl;
}
std::queue<xin_tim>q; q.push(xin_tim(1,0)); int pot,now = 0;
memset(vis,0,sizeof(bool) * (n + 1));vis[1] = 1;
while(q.size())
{
xin_tim x = q.front(); q.pop();
// sb(x.tim);jb(x.x);
if(x.tim > now) now = x.tim,pot = x.x;
go(i,x.x) if(!vis[y])
{
vis[y] = 1; q.push(xin_tim(y,x.tim+1));
}
}
// jb(pot);
// jb(now);
q.push(xin_tim(pot,0)); now = 0;
memset(vis,0,sizeof(bool ) * (n + 1)); vis[pot] = 1;
while(q.size())
{
xin_tim x = q.front(); q.pop();
if(x.tim > now) now = x.tim;
go(i,x.x) if(!vis[y]) vis[y] = 1,q.push(xin_tim(y,x.tim+1));
}
// jb(now);
// if(now == 1) cout<<0<<endl;
cout<<(now+1)/2<<endl;
return 0;
}
}
signed main() {return xin::main();}
话说我好像把昨天写的丢了。。
Day -21
话说为什么昨天还是-23
似乎我从刚开始就记错了。。。
今天还是有模拟赛的一天，没有什么口胡比赛。。
并且还是毒瘤出题人 \(JKLover\) 的sb好题
莓良心
这个其中很关键的一步就是求集合的划分。
这个需要用到第二类斯特林数
但是这个东西到考场上却忘记了怎么推了。。
这个就是方案就是斯特林嘛。。
那怎么求呢？？
。。。。。
顺带复习一下子。
\(\begin {Bmatrix} n \\ m\end {Bmatrix}\) 就表示有 \(n\) 个数，划分为 \(k\) 个非空子集的方案数。
那么这个东西如何在小于xin_team的时间复杂度求出呢？？
首先有一个 \(n^2\) 的递推。
\[\begin {Bmatrix} n \\ k \end {Bmatrix}=\begin {Bmatrix} n-1\\k-1 \end {Bmatrix}+k\begin {Bmatrix} n-1\\k \end {Bmatrix} \]然后初值就是 \(\begin {Bmatrix} n \\ 0 \end {Bmatrix}=[n=0]\)
当然还有通项公式：
\[\begin {Bmatrix} n \\ k \end {Bmatrix}=\frac{\sum_{i=0}^{k}(-1)^i\dbinom{k}{i}(k-i)^n}{k!} \]似乎是通过一个容斥得出的。
只不过这玩意是 \(nlog\) 的。。
还有一个性质，似乎感觉自己也是背不过。。。
\[n^k=\sum_{i=0}^k\begin {Bmatrix} k \\ i \end {Bmatrix}×i!×\dbinom{n}{i} \]code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define scanf ak = scank
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10;
#define int long long
namespace xin
{
const int mod = 998244353;
int a[maxn];
int n,k;
int he;
int s1,s2;
int fac[maxn],inv[maxn];
auto C = [](int n,int m) {return fac[n] * inv[m] % mod * inv[n-m] % mod;};
inline int ksm(int x,int y,int ret = 1)
{
while(y)
{
if(y & 1) ret = ret * x % mod;
x = x * x % mod;y >>= 1;
}
return ret;
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(ichigo);
#endif
io >> n >> k;
try(i,1,n) io >> a[i],he += a[i],he %= mod;
fac[0] = inv[0] = 1;
try(i,1,k) fac[i] = fac[i-1] * i % mod;
inv[k] = ksm(fac[k],mod-2);
throw(i,k-1,1) inv[i] = inv[i+1] * (i + 1) % mod;
// jb(C(2,1));
int base = 1;
try(i,0,k)
{
(s1 += base * C(k,i) % mod * ksm(k-i,n) % mod + mod) %= mod;
// jb(s1);
(s2 += base * C(k,i) % mod * ksm(k-i,n-1) % mod + mod) %= mod;
// jb(s2);
base = -base;
}
// jb(s1); jb(s2);
cout<<he * ((s1 + (n - 1) * s2 % mod) % mod) % mod * inv[k] % mod<<endl;
return 0;
}
}
signed main() {return xin::main();}
``
</details>
**尽梨了**
这个主要的问题还是在 $dp$ 上面，如果没有进行排序，那么这个需要的 $dp$ 就会是从这些集合当中不重复的选择。
似乎这个只有背包可以完成，但是体积直接达到了 $10^9$
所以正确的解法应该是消除一个的限制。
我们首先明确哪个顺序一定是优的。
之后再进行 $dp$ 才可。
<details>
<summary>code</summary>
```cpp
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+10; const ll llinf = 1e18+10;
#define int long long
namespace xin
{
class xin_data
{
public:
int x,y;
xin_data(){}
xin_data(int x,int y):x(x),y(y){}
}d[maxn];
int a[maxn];
int n,tim;
int cnt1,cnt2;
int f[maxn][33];
inline bool comp(const xin_data &x,const xin_data &y) {return x.y * y.x < x.x * y.y;}
inline short main()
{
#ifdef ONLINE_JUDGE
file(eriri);
#endif
io >> n >> tim;
try(i,1,n)
{
register int x,y; io >> x >> y; y += x + 1;
if(!x) a[++cnt2] = y;
else d[++cnt1] = xin_data(x,y);
}
std::sort(d+1,d+cnt1+1,comp); std::sort(a+1,a+cnt2+1);
memset(f,0x3f,sizeof(f)); f[0][0] = 0;
// try(i,1,cnt1) sb(d[i].x),jb(d[i].y);
try(i,0,cnt1-1) try(j,0,32) if(f[i][j] <= tim)
{
f[i+1][j] = std::min(f[i+1][j],f[i][j]);
int temp = (f[i][j] + 1) * (d[i+1].x + 1) + (d[i+1].y - d[i+1].x - 1);
// jb(temp);
if(temp <= tim) f[i+1][j+1] = std::min(f[i+1][j+1],temp);
}
int pos = 0,ans = 0,he = 0;
throw(i,32,0) if(f[cnt1][i] <= tim)
{
while(pos != cnt2 and he + f[cnt1][i] + a[pos+1] <= tim)
he += a[++pos];
ans = std::max(ans,pos + i);
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
团不过
考虑在限定每堆石子数目互不相同的前提下，用所有方案数减去先手必败的方
案数。
设 \(p(i) = (2n −1)^{\underline i}\) ，即 \(i\) 堆石子的总方案数。
设 \(f(i)\) 表示 \(i\) 堆石子时先手必败的方案数。
我们考虑让前 \(i −1\) 堆石子任意取，通过调整最后一堆石子的数目使得异或和为\(0\) ，方案数为 \(p(i −1)\) 。
若前 \(i −1\) 堆石子异或和为 \(0\) ，因为最后一堆不能取 \(0\) ，这种情况是不合法的，
方案数为 \(f(i −1)\) 。
若前 \(i −1\) 堆石子中，有 \(i −2\) 堆石子异或起来是 \(0\) ，那么最后一堆石子就只能
和另一堆石子数目相同，也是不合法的，方案数为 \((i −1) ·(2n −i + 1) ·f(i −2)\) 。
于是得到 \(f(i) = p(i −1) −f(i −1) −(i −1) ·(2n −i + 1) ·f(i −2)\) ，边界为
\(f(1) = f(2) = 0\) ，直接 \(\mathcal O(n)\) 递推即可
关于下降幂。。
\[x^{\underline i}=x(x-1)(x-2)....(x-i+1) \] \[x^{\underline i}=\frac{x!}{(x-i)!} \]code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+10; const ll llinf = 1e18+10;
#define int long long
namespace xin
{
const int mod = 1e9+7;
int f[maxn],fac[maxn],inv[maxn],n,p[maxn];
inline int ksm(int x,int y,int ret = 1)
{
while(y)
{
if(y & 1) ret = ret * x % mod;
x = x * x % mod; y >>= 1;
}
return ret;
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(yui);
#endif
io >> n;
fac[0] = inv[0] = 1; int pow2 = ksm(2,n);
try(i,1,n) fac[i] = fac[i-1] * i % mod;
p[1] = pow2 - 1;
try(i,2,n) p[i] = p[i-1] * (pow2 - i) % mod;
inv[n] = ksm(fac[n],mod-2);
throw(i,n-1,1) inv[i] = inv[i+1] * (i + 1) % mod;
// jb(p(2));
// return 0;
try(i,3,n) f[i] = (p[i-1] - f[i-1] - (i - 1) * (pow2 - i + 1) % mod * f[i-2] % mod + mod) % mod;
cout<<(p[n] - f[n] + mod) % mod <<endl;
return 0;
}
}
signed main() {return xin::main();}
七负我
这个有一个结论。
就是这个题目我们要找到图中的最大团。
然后平均分配就是答案。
忘了怎么证明的了。
然后状态压缩一下，之后 \(meet\;in\;middle\) 就好了
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define debug std::cerr<<"debug"<<endl
#define sb(x) std::cerr<<#x" = "<<x<<' '
#define jb(x) std::cerr<<#x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f = 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+10; const ll llinf = 1e18+10;
#define int long long
namespace xin
{
inline void out(int x)
{
cout<<"x = ";
int st = 0;
throw(i,30,1) if(x & (1 << i - 1)) {st = i; break;}
throw(i,st,1) cout<<(bool)(x & (1 << i - 1));
cout<<endl;
}
int f[maxn];
int n,m,tim;
int a[maxn],cnt[maxn];
auto get = [](int x)
{
int ret = 0;
while(x) ret += x & 1,x >>= 1;
return ret;
};
inline short main()
{
#ifdef ONLINE_JUDGE
file(nanami);
#endif
io >> n >> m >> tim;
a[1] = 1; try(i,2,40) a[i] = a[i-1] << 1;//,out(a[i]);
int mid = (n + 1) >> 1;
try(i,1,m)
{
register int x,y; io >> x >> y;
a[x] |= 1ll << y - 1; a[y] |= 1ll << x - 1;
}
// try(i,1,3) out(a[i]);
try(s,1,(1 << mid)) cnt[s] = get(s);
try(s,1,(1 << mid) - 1)
{
// int num = 0;
int temp = -1;
try(i,1,mid) if(s & (1 << i - 1)) f[s] = std::max(f[s],f[s xor (1 << i - 1)]),temp &= a[i];
// out(temp);
// jb(cnt[s]);
if((s & temp) == s) f[s] = cnt[s];
// sb(s); jb(f[s]);
}
int ms = n - mid,ans = 0;
try(s,1,(1 << ms) - 1)
{
int temp = -1;
try(i,1,ms) if(s & (1 << i - 1)) temp &= a[i+mid];
// jb(cnt[s]);
// jb(temp);
if((temp & (s << mid)) == (s << mid))
ans = std::max(ans,cnt[s] + f[temp & (1ll << mid) - 1]);//,jb(temp),jb(mid);
}
// jb(ans);
printf("%.6lf\n",(1.0 * tim / ans) * (1.0 * tim / ans) * (ans * (ans - 1)) * 0.5);
return 0;
}
}
signed main() {return xin::main();}
所以这个题目的难处就是在求这个图的最大团上面了。
然而似乎这个问题是 \(NP\) 完全的。
Day -20
;
话说我为啥老是丢掉之前写的博客啊。。
还是模拟赛日。
然后拿了倒数
特殊字符串
首先上来的 \(dp\) 一看没有小样例，直接就跳过了。
然后发现。。
一共。。。
\(68\) 人写过。。
然后我。。
为啥没有去再看看呢
其实就是直接 \(dp\)。
我们设 \(f_{i,j}\) 表示前 \(i\) 个串结尾强制为 \(j\) 这个字母的映射的答案。
那么直接就是
\[f_{i,j} = \max_{k=1}^{26}f_{i-1,k} + a_{k,j} \]\(a_{k,j}\) 就是输入的贡献。
然后呢。。。
没了。。
我也没了。。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
// #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
#define gc() getchar()
#define debug std::cerr<<"debug"<<endl
#define scanf ak = scanf
char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 2e3+10,inf = 1e9+10;
#define int long long
namespace xin
{
int a[27][27];
int f[maxn][27];
int n;
char s[maxn];
char s1[maxn],s2[maxn];
inline short main()
{
freopen("shiki.in","r",stdin); freopen("shiki.out","w",stdout);
io >> n;
scanf("%s",s+1);
int m; io >> m;
try(i,1,m)
{
int k;
scanf("%s%s",s1+1,s2+1); io >> k;
a[s1[1] - 'a' + 1][s2[1] - 'a' + 1] += k;
}
int ans = 0;
memset(f,128,sizeof(f));
// jb(f[1][1]);
try(i,1,n)
{
int j = s[i] - 'a' + 1;
f[i][j] = 0;
try(k,1,26)
f[i][j] = std::max(f[i][j],f[i-1][k] + a[k][j]),f[i][k] = std::max(f[i][k],f[i-1][k]);
ans = std::max(f[i][j],ans);
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
宝可梦
别问我为啥对pokemon有一种特殊的情结。
所以我上来就做这个题了。
刚上来发现这个题目是一个大模拟，然后认为需要投入很长的时间。
然后疯狂开始码，然后半个小时写完了。
然后发现这个有一个 \(n=2\) 的部分分数，然后想到了似乎这个只有一条路径。
但是为啥我没有推广一下子呢，其实所有的图都是只有一条路径的啊。
暴力的想法其实就是每次给出的两个坐标都模拟一遍。
但是这样只有垃圾的 \(40pts\)。
因为每一个空闲点一定会被走过至少一次，那么我们可以任意找到一个空白点，之后试探四个方向哪个可以开始走，这样我们就找到了其中的一个点了。
从这个点开始，我们一定可以走完这个图中唯一的道路，这样我们记录一下坐标和它的方向，然后记录走到这个位置的相对时间。
对于每一次询问，做一下差就行了，只不过要注意一下方向等细节。
然后我获得了次垃解
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gec() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<22,stdin),p1 == p2) ? EOF : *p1 ++
#define gc() getchar()
#define debug std::cerr<<"debug"<<endl
#define scanf ak = scanf
char buf[1<<22],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 2e3+10,inf = 1e9+10;
// #define int long long
namespace xin
{
int n,m;
std::vector<int> a[maxn/2];
char s[maxn];
class xin_data
{
public:
int x,y;
xin_data(){}
xin_data(int x,int y):x(x),y(y){}
};
auto you = [](const xin_data &x,int type)
{
if(type == 1) return xin_data(x.x,x.y+1);
else if(type == 2) return xin_data(x.x,x.y-1);
else if(type == 3) return xin_data(x.x-1,x.y);
else return xin_data(x.x+1,x.y);
};
auto qian = [](const xin_data &x,int type)
{
if(type == 1) return xin_data(x.x-1,x.y);
else if(type == 2) return xin_data(x.x+1,x.y);
else if(type == 3) return xin_data(x.x,x.y-1);
else return xin_data(x.x,x.y+1);
};
inline int get(char ch)
{
if(ch == 'U') return 1;
else if(ch == 'D') return 2;
else if(ch == 'L') return 3;
else return 4;
}
auto zz = [](int type)
{
if(type == 1) return 3;
else if(type == 2) return 4;
else if(type == 3) return 2;
else return 1;
};
auto yz = [](int type)
{
if(type == 1) return 4;
else if(type == 2) return 3;
else if(type == 3) return 1;
else return 2;
};
class xin_map
{
private:
friend bool operator < (const xin_map &x,const xin_map &y)
{
if(x.x xor y.x) return x.x < y.x;
if(x.y xor y.y) return x.y < y.y;
return x.nt < y.nt;
}
public:
int x,y,nt;
xin_map(){}
xin_map(int x,int y,int nt):x(x),y(y),nt(nt){}
};
std::map<xin_map,int>vis;
auto query = [](xin_data now,xin_data goal,char type)
{
int ret = 0,nt = get(type),gt = nt;
xin_data pre = xin_data(0,0);
now = qian(now,nt); ret ++;
vis[xin_map(now.x,now.y,nt)] = ret;
while(now.x != goal.x or now.y != goal.y or nt != gt)
{
// vis[xin_map(now.x,now.y,nt)] = ret;
// sb(now.x); sb(now.y); jb(ret);
if(!a[you(now,nt).x][you(now,nt).y])
{
while(!a[qian(now,nt).x][qian(now,nt).y])
{
if(now.x == goal.x and now.y == goal.y and nt == gt) return ret;
nt = zz(nt);
if(now.x == goal.x and now.y == goal.y and nt == gt) return ret;
}
now = qian(now,nt); ret ++;
vis[xin_map(now.x,now.y,nt)] = ret;
}
else
{
now = you(now,nt); ret ++;
nt = yz(nt);
vis[xin_map(now.x,now.y,nt)] = ret;
}
}
return ret;
};
inline char get_alpha(int x)
{
if(x == 1) return 'U';
else if(x == 2) return 'D';
else if(x == 3) return 'L';
else return 'R';
}
inline void init(int &tot)
{
try(i,1,n) try(j,1,m)
{
try(t,1,4)
{
if(a[i][j] and a[qian(xin_data(i,j),t).x][qian(xin_data(i,j),t).y])
{
// debug;
tot = query(xin_data(i,j),xin_data(i,j),get_alpha(t));
// ok = 1;
return;
}
}
}
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(pokemon);
#endif
scanf("%d%d",&n,&m);
try(i,1,m) a[0].emplace_back(0),a[n+1].emplace_back(0);
try(i,1,n)
{
a[i].emplace_back(0);
scanf("%s",s+1);
try(j,1,m) a[i].emplace_back((s[j] == '.'));//,cout<<a[i][j];
a[i].emplace_back(0);
a[i].reserve(m + 10);
// cout<<endl;
}
int qnum; scanf("%d",&qnum);
int tot; init(tot);
// jb(query(xin_data(1,1),xin_data(1,1),'R'));
// jb(tot);
// try(i,1,n) {try(j,1,m) cout<<std::setw(4)<<vis[xin_map(i,j,1)]; cout<<endl;}cout<<endl;
// try(i,1,n) {try(j,1,m) cout<<std::setw(4)<<vis[xin_map(i,j,2)]; cout<<endl;}cout<<endl;
// try(i,1,n) {try(j,1,m) cout<<std::setw(4)<<vis[xin_map(i,j,3)]; cout<<endl;}cout<<endl;
// try(i,1,n) {try(j,1,m) cout<<std::setw(4)<<vis[xin_map(i,j,4)]; cout<<endl;}cout<<endl;
try(cse,1,qnum)
{
register int x,y,goalx,goaly;
scanf("%d%d%d%d%s",&x,&y,&goalx,&goaly,s+1);
if(x == goalx and y == goaly) {puts("0"); continue;}
int ans = inf;
try(i,1,4)
if(vis[xin_map(goalx,goaly,i)])
{
int temp = (vis[xin_map(goalx,goaly,i)] - vis[xin_map(qian(xin_data(x,y),get(s[1])).x,qian(xin_data(x,y),get(s[1])).y,get(s[1]))]);
// jb(temp);
if(temp < 0) temp += tot;
ans = std::min(ans,temp + 1);
}
if(ans < 0) ans += tot;
printf("%d\n",ans);
// cout<<ans<<endl;
// sb(vis[xin_map(goalx,goaly,1)]); jb(vis[xin_map(x,y,get(s[1]))]);
// printf("%d\n",vis[xin_map(goalx,goaly,4)] - vis[xin_map(x,y,get(s[1]))]);
// printf("%d\n",query(xin_data(x,y),xin_data(goalx,goaly),s[1]));
}
return 0;
}
}
signed main() {return xin::main();}
矩阵
直接搜索就行，因为大概率搜不下去。
code
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
#define sb(x) std::cerr << #x" = "<<x<<' '
#define jb(x) std::cerr << #x" = "<<x<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<22,stdin),p1 == p2) ? EOF : *p1 ++
// #define gc() getchar()
#define debug std::cerr<<"debug"<<endl
char buf[1<<22],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long;
class xin_stream{public:template<typename type>xin_stream operator >> (type &s)
{
s = 0; register bool f= 0; register char ch = gc();
while(!isdigit(ch)) f |= ch == '-',ch = gc();
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 2e3+10,inf = 1e9+10;
// #define int long long
namespace xin
{
const int dx[] = {0,0,-1,1},dy[] = {1,-1,0,0};
int *a[40002];
int n,m;
bool sp = 1;
class xin_data
{
public:
int x,y,bei,tim;
xin_data(){}
xin_data(int x,int y,int bei = 0,int tim = 0):x(x),y(y),bei(bei),tim(tim){}
}q[maxn];
int zhi = 0,ans,cnt;
void bfs(const xin_data &now)
{
q[zhi = 1] = now;
int ms = 1e7;
while(zhi)
{
xin_data x = q[zhi--];
if(cnt >= ms) {cout<<(1<<4)<<endl; exit(0);}
try(i,0,3)
{
xin_data p = xin_data(x.x + dx[i],x.y + dy[i]);
if(p.x >= 1 and p.x <= n and p.y >= 1 and p.y <= m)
{
++cnt;
if(a[p.x][p.y] % a[x.x][x.y] == 0 and (!x.bei or (x.bei and a[p.x][p.y] / a[x.x][x.y] == x.bei)))
{
q[++zhi] = xin_data(p.x,p.y,a[p.x][p.y] / a[x.x][x.y],x.tim + 1);
// jb(x.tim + 2);
ans = std::max(ans,x.tim + 2);
}
}
}
}
}
inline short main()
{
#ifdef ONLINE_JUDGE
file(matrix);
#endif
io >> n >> m;
if(n == 1 and m == 1) return puts("1"),0;
// if(n >= 5000) return cout<<10<<endl,0;
// try(i,0,m+1) a[0].emplace_back(0),a[n+1].emplace_back(0);
a[0] = new int [m + 2]; a[n+1] = new int [m + 2];
try(i,1,n)
{
a[i] = new int [m + 2];
try(j,1,m)
{
int x; io >> x; a[i][j] = x;
// if(j - 1 and a[i][j] != a[i][j-1]) sp = 0;
if((i - 1 and a[i][j] == a[i-1][j]) or (j - 1 and a[i][j] == a[i][j-1]))
return puts("-1"),0;
}
// a[i].emplace_back(0);
// a[i].reserve(m + 10);
}
// if(sp) {puts("-1"); return 0;}
try(i,1,n) try(j,1,m) bfs(xin_data(i,j));
jb(cnt);
cout<<std::max(ans,1)<<endl;
return 0;
}
}
signed main() {return xin::main();}
乘法
别问，问就是做不出来。
但是这个题目的分段打表属实涨知识了。
可以拿到 \(30pts\) 的高分。
但是为啥我的暴力没有一点分呢。。。
下午5:10
教练：一会儿可以出去玩儿会儿。
然后开始乒乓球颓废生活。
fengwu:我要打爆七百信。
然后。。。
\[5:0 \]fengwu自闭。
晚上8:00
太虚：出分了。
机房哗然，然后开始查分。
发现沈队一旁镇定地查分，丝毫不慌。
再怎么挂也是HE rk1
然后土豆服务器被挤爆了，几乎没有几个人能够上去。
之后摇摆b首先查到分数，然后他第一个题目的 \(40pts\) 被 \(CCF\) 的数据抬到了 \(60pts\)。
表示羡慕。
之后终于看到分数，发现自己四处爆零的廊桥分配竟然有 \(55pts\)，突然开始感谢 \(CCF.jpg\)
四处爆零
话说沈队真的是 \(360pts\)
Day -19
今天并没有模拟赛。
昨天看的垃圾 \(dp\) 守望者的逃离今天决定扔掉。
因为没有一个题解写的 \(dp\)
做了一个教主的花园
教主的花园
以为是区间 \(dp\)，但是似乎并不能用区间 \(dp\) 转移。
首先如果不考虑这个是一个环的话，那么我们直接可以从 \(1\) 推到 \(n\)。
那这样该怎么列 \(dp\) 方程呢。
我们设 \(f_{i,0/1/2,0/1}\) 分别表示前 \(i\) 个，第 \(i\) 个选择了哪种树苗，之后是否比旁边的高的答案。
那么这样就分类转移。
- \(f_{i,0,0} = \max(f_{i-1,1,1},f{i-1,2,1})+a_{i,0}\)
- \(f_{i,1,0} = f_{i-1,2,1}+a_{i,1}\)
- \(f_{i,1,1} = f_{i-1,0,0}+a_{i,1}\)
- \(f_{i,2,1} = \max(f_{i-1,0,0},f_{i-1,1,0})+a_{i,0}\)
这个的意义还是比较明显的。
剩下的就是我们要考虑这个东西是一个环的情况了。
如果这个是一个环，那么我们还要考虑 \(1\) 和 \(n\) 的关系。
这个因为其实只有 \(3\) 种状态，枚举一下 \(1\) 选择的树苗，然后分别做一次 \(dp\) 就好了。
最后选择合法的方案统计答案。