Preface
传说中被杭电 1h 十题的比赛，结果打到结束也只会 10 题
这场开局就不太顺，一个 Easy 题 C 卡到 2h 的时候才出，虽然中期题基本都能想到但还是出的很慢
最后 1h 讨论了下 L 的大致做法发现了几个关键性质后觉得写不完了，遂摆烂滚去打炉石了
A. Printer
签到，二分答案大力检验即可，注意实现不当可能会爆 long long
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=105,INF=2e18;
int T,n,k,t[N],l[N],w[N];
inline bool check(CI lim)
{
int sum=0;
for (RI i=1;i<=n;++i)
{
int s=lim/(t[i]*l[i]+w[i]); sum+=s*l[i];
int left=lim-s*(t[i]*l[i]+w[i]);
if (left>=t[i]*l[i]) sum+=l[i]; else sum+=left/t[i];
if (sum>=k) return 1;
}
return sum>=k;
}
signed main()
{
for (scanf("%lld",&T);T;--T)
{
scanf("%lld%lld",&n,&k);
for (RI i=1;i<=n;++i) scanf("%lld%lld%lld",&t[i],&l[i],&w[i]);
int l=1,r=INF,ret=-1;
while (l<=r)
{
int mid=l+r>>1;
if (check(mid)) ret=mid,r=mid-1; else l=mid+1;
}
printf("%lld\n",ret);
}
return 0;
}
C. Colorful Segments 2
神秘题，刚开始 Rush 了一个按右端点排序然后算方案数的东西，结果发现有问题
思考了很久之后徐神提出按左端点排序后差分一下就可以了，然后就淦过去了，我至今不明原理
#include <bits/stdc++.h>
using llsi = long long;
constexpr llsi mod = 998244353;
void work() {
int n, k; std::cin >> n >> k;
llsi ans = 1;
std::vector<std::pair<int, int>> event;
for(int i = 0, l, r; i < n; ++i) {
std::cin >> l >> r;
event.emplace_back(l, 1);
event.emplace_back(r + 1, -1);
}
std::sort(event.begin(), event.end());
llsi sum = 0;
for(auto [p, v]: event) {
// std::cout << p << " " << v << char(10);
if(v == 1) ans = ans * std::max(0LL, k - sum) % mod;
sum += v;
}
std::cout << ans << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
D. Hero of the Kingdom
考虑最优决策过程，肯定是前面一段操作购买的物品量被钱数 bound，后面一段操作购买的物品量被时间 bound
不难发现一旦进入被时间 bound 的阶段时整个过程就结束了，因此我们只需要模拟前面一段被钱数 bound 的过程即可
朴素的实现可能会被 \(p-q\) 很小的数据给卡掉，因此我们要把所有 \(\lfloor\frac{m}{p}\rfloor\) 相同的购买操作一起处理，直到 \(\lfloor\frac{m}{p}\rfloor\) 的值发生变化
由于 \(\lfloor\frac{m}{p}\rfloor\) 的值每次至少增加 \(1\)，因此在根号级别的操作次数后就会进入被时间 bound 的阶段
#include<bits/stdc++.h>
using namespace std;
#define int long long
int solve() {
int p, a, b; cin >> p >> a >> b;
int q, c, d; cin >> q >> c >> d;
int m, t; cin >> m >> t;
while (1) {
if (m < p) break;
int s = m/p;
int l = (p - m%p + (q-p)*s -1) / ((q-p)*s);
int ts = (s*(a+c) + (b+d));
int tt = l*ts;
// printf("m=%lld t=%lld s=%lld l=%lld ts=%lld tt=%lld\n", m, t, s, l, ts, tt);
if (tt > t) {
m += (t / ts) * s * (q-p);
t %= ts;
// printf("1111\n");
// printf("m=%lld t=%lld\n", m, t);
if (t < a+b+c+d) break;
int nx = (t-(b+d))/(a+c);
t -= nx*(a+c) + (b+d);
m += (q-p)*nx;
break;
}
t -= tt;
m += (q-p)*s*l;
}
return m;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) cout << solve() << '\n';
return 0;
}
E. Sensors
神秘势能分析题
考虑用线段树分治的思想，把一个区间在线段树上分成 \(\log n\) 段区间
一个朴素的想法就是每次修改一个值时，将经过的线段树的所有节点上对应的区间的贡献都修改一下，但这样显然会被卡掉
但我们仔细思考会发现，当线段树上某个点的点权和从一个 \(x>3\) 的值变为 \(x-1\) 时，对应的所有区间都不可能发生贡献变化
因此只要在点权和为 \(1/0\) 时才大力更新，复杂度就是对的了
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int t,n,m,l,r,bkt[N],x; long long ans;
vector <int> lst[N];
class Segment_Tree
{
private:
vector <pair <int,int>> vec[N<<2]; int sum[N<<2];
inline void reset(CI x)
{
for (auto [id,pos]:vec[x])
{
if (bkt[id]==1) ans-=1LL*id*id;
bkt[id]-=lst[id][pos];
lst[id][pos]=sum[x];
bkt[id]+=lst[id][pos];
if (bkt[id]==1) ans+=1LL*id*id;
}
}
public:
#define TN CI now=1,CI l=0,CI r=n-1
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
sum[now]=r-l+1; vec[now].clear(); if (l==r) return;
int mid=l+r>>1; build(LS); build(RS);
}
inline void insert(CI beg,CI end,CI id,TN)
{
if (beg<=l&&r<=end)
{
lst[id].push_back(r-l+1);
vec[now].push_back({id,lst[id].size()-1});
return;
}
int mid=l+r>>1; if (beg<=mid) insert(beg,end,id,LS); if (end>mid) insert(beg,end,id,RS);
}
inline void update(CI pos,TN)
{
if (l==r)
{
sum[now]=0; reset(now); return;
}
int mid=l+r>>1; if (pos<=mid) update(pos,LS); else update(pos,RS);
sum[now]=sum[now<<1]+sum[now<<1|1];
if (sum[now]==0||sum[now]==1) reset(now);
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
// freopen("E.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=m;++i) lst[i].clear();
SEG.build(); ans=0;
for (RI i=1;i<=m;++i)
{
scanf("%d%d",&l,&r);
bkt[i]=r-l+1; SEG.insert(l,r,i);
if (bkt[i]==1) ans+=1LL*i*i;
}
printf("%lld ",ans);
for (RI i=1;i<=n;++i)
{
scanf("%d",&x); x=(x+ans)%n;
SEG.update(x); printf("%lld%c",ans," \n"[i==n]);
}
}
return 0;
}
F. Divide the Sequence
祁神开场写的签，我题目都没看
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n, A[N], shuf[N];
void solve() {
cin >> n;
for (int i=1; i<=n; ++i) cin >> A[i];
shuf[n+1] = 0;
for (int i=n; i>0; --i) shuf[i] = shuf[i+1]+A[i];
int ans = shuf[1];
vector<int> vec;
for (int i=2; i<=n; ++i) vec.push_back(shuf[i]);
sort(vec.begin(), vec.end(), greater<int>());
for (int i=1; i<=n; ++i) {
cout << ans << ' ';
if (i-1<vec.size()) ans += vec[i-1];
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
H. Stop the Castle
思路不难想到，但实现比较需要耐心的一个题
考虑如果一行或者一列有多个车，那么其实只要考虑相邻的一对不冲突即可
同时由于新建一个障碍至少可以 fix 一对车，至多只能 fix 两对车，因此考虑最大化能 fix 两对车的障碍数即可
考虑将横着的一对车看作二分图的左部点，竖着的一对车看作二分图的右部点，如果存在一个位置能同时 fix 这两对车的话就给这两个点之间连边
求出最大匹配后，将匹配的交点处放上障碍；剩下的非匹配点就在旁边随便放个障碍即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=205;
int t,n,m,mat[N],vis[N],ok[N]; pair <int,int> c[N],o[N]; vector <int> v[N];
inline bool find(CI now,CI idx)
{
for (auto to:v[now]) if (vis[to]!=idx)
{
vis[to]=idx;
if (mat[to]==-1||find(mat[to],idx))
return mat[to]=now,1;
}
return 0;
}
int main()
{
// freopen("H.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=1;i<=n;++i)
scanf("%d%d",&c[i].fi,&c[i].se);
scanf("%d",&m);
for (RI i=1;i<=m;++i)
scanf("%d%d",&o[i].fi,&o[i].se);
vector <pair <int,int>> L,R; bool flag=1;
for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
{
if (c[i].fi!=c[j].fi) continue;
int l=c[i].se,r=c[j].se;
if (l>r) swap(l,r);
if (l+1==r) flag=0;
bool sign=1;
for (RI k=1;k<=m;++k)
if (o[k].fi==c[i].fi&&l<o[k].se&&o[k].se<r) sign=0;
for (RI k=1;k<=n;++k)
{
if (i==k||j==k) continue;
if (c[k].fi==c[i].fi&&l<c[k].se&&c[k].se<r) sign=0;
}
if (sign) L.push_back({i,j});
}
for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
{
if (c[i].se!=c[j].se) continue;
int l=c[i].fi,r=c[j].fi;
if (l>r) swap(l,r);
if (l+1==r) flag=0;
bool sign=1;
for (RI k=1;k<=m;++k)
if (o[k].se==c[i].se&&l<o[k].fi&&o[k].fi<r) sign=0;
for (RI k=1;k<=n;++k)
{
if (i==k||j==k) continue;
if (c[k].se==c[i].se&&l<c[k].fi&&c[k].fi<r) sign=0;
}
if (sign) R.push_back({i,j});
}
if (!flag) { puts("-1"); continue; }
for (RI i=0;i<L.size();++i) v[i].clear();
// for (auto [x,y]:L) printf("L:(%d,%d)\n",x,y);
// for (auto [x,y]:R) printf("R:(%d,%d)\n",x,y);
for (RI i=0;i<L.size();++i)
for (RI j=0;j<R.size();++j)
{
int X=c[L[i].fi].fi,Y=c[R[j].fi].se;
int xl=c[R[j].fi].fi,xr=c[R[j].se].fi;
int yl=c[L[i].fi].se,yr=c[L[i].se].se;
if (xl>xr) swap(xl,xr);
if (yl>yr) swap(yl,yr);
if (X<=xl||X>=xr||Y<=yl||Y>=yr) continue;
v[i].push_back(j);
}
memset(vis,-1,sizeof(vis));
memset(ok,-1,sizeof(ok));
memset(mat,-1,sizeof(mat));
for (RI i=0;i<L.size();++i) find(i,i);
vector <pair <int,int>> ans;
for (RI i=0;i<R.size();++i)
if (mat[i]!=-1)
{
int u=mat[i],v=i; ok[u]=1;
int X=c[L[u].fi].fi,Y=c[R[v].fi].se;
ans.push_back({X,Y});
}
for (RI i=0;i<L.size();++i)
if (ok[i]==-1)
{
auto [u,v]=L[i];
int l=c[u].se,r=c[v].se;
if (l>r) swap(l,r);
ans.push_back({c[u].fi,l+1});
}
for (RI i=0;i<R.size();++i)
if (mat[i]==-1)
{
auto [u,v]=R[i];
int l=c[u].fi,r=c[v].fi;
if (l>r) swap(l,r);
ans.push_back({l+1,c[u].se});
}
printf("%d\n",(int)ans.size());
for (auto [x,y]:ans) printf("%d %d\n",x,y);
}
return 0;
}
I. Left Shifting
祁神开场写的签，我题目都没看
#include<bits/stdc++.h>
using namespace std;
int solve() {
string str; cin >> str;
int n = str.length();
if (1==n || str[0]==str[n-1]) return 0;
for (int i=1; i<n; ++i) if (str[i]==str[i-1]) return i;
return -1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) cout << solve() << '\n';
return 0;
}
J. Colorful Spanning Tree
刚开始写类普利姆的东西把自己写红温了，后面改成类克鲁斯卡尔的东西发现贼好写
考虑对于两种颜色 \(u,v\)，维护它们各自内部还有 \(sz_u,sz_v\) 个联通块
合并的时候若 \(u\ne v\)，则可以连 \(sz_u+sz_v-1\) 条边；否则可以连 \(sz_u-1\) 条边
拿个并查集随便搞一搞就行了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,INF=1e18;
int t,n,fa[N],sz[N],mn[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld",&n); int ans=0;
for (RI i=1;i<=n;++i) fa[i]=i,scanf("%lld",&sz[i]);
vector <array <int,3>> E;
for (RI i=1;i<=n;++i)
for (RI j=1;j<=n;++j)
{
int w; scanf("%lld",&w);
E.push_back({w,i,j});
}
sort(E.begin(),E.end());
for (auto [w,u,v]:E)
{
u=getfa(u); v=getfa(v);
if (u==v) ans+=w*(sz[u]-1),sz[u]=1;
else ans+=w*(sz[u]+sz[v]-1),fa[v]=u,sz[u]=1,sz[v]=0;
}
printf("%lld\n",ans);
}
return 0;
}
K. Matrix
很一眼的构造题
前 \(n-2\) 行每行分别全部放 \(1,2,\dots,n-2\)，这样题目要求的矩形就不可能在上面取了
剩下的最后两行用以下方式摆放即可：
\[\begin{align} & n-1,n,n+1,\dots,2n-4,2n-3,2n-2\\ & n-1,n,n+1,\dots,2n-4,2n-1,2n \end{align} \]#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int n,a[N][N];
int main()
{
scanf("%d",&n);
for (RI i=1;i<=n-2;++i)
for (RI j=1;j<=n;++j) a[i][j]=i;
for (RI j=1;j<=n-2;++j) a[n-1][j]=a[n][j]=n-2+j;
a[n-1][n-1]=2*n-3; a[n-1][n]=2*n-2;
a[n][n-1]=2*n-1; a[n][n]=2*n;
puts("Yes");
for (RI i=1;i<=n;++i)
for (RI j=1;j<=n;++j)
printf("%d%c",a[i][j]," \n"[j==n]);
return 0;
}
L. Intersection of Paths
比赛最后推了几个性质后发现大概率写不完就懒得写了，后面发现其实有机会 30min 淦出来的
考虑一条 \((u,v)\) 的路径是否可以 fix 一个参数为 \(k\) 的询问，其实就是看 \(u,v\) 两侧的子树都要有至少 \(k\) 个点
直接想路径的话不好处理，考虑把限制放到一条边上，显然对于一个固定的 \(k\) 我们对所有满足要求的边求一个直径就是答案
因此求出每条边的边权后离线处理一下即可，可以用经典 trick 解决，代码就先坑着后面再来补吧
M. Palindromic Polygon
徐神和祁神开场就讨论出来的一个神秘几何题，后面发现这题其实还挺难的
由于我题意都不知道就不做评论了，大致就是列出显然的 \(O(n^4)\) DP 方程后把面积部分用前缀和优化一下变成 \(O(n^3)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
struct vivi {
llsi x, y;
friend vivi operator -(const vivi &a, const vivi &b) {
return {a.x - b.x, a.y - b.y};
}
llsi crs(const vivi &b) {
return x * b.y - y * b.x;
}
};
llsi area(const vivi &a, const vivi &b, const vivi &c) {
return std::abs((c - a).crs(b - a));
}
int n, f[1005];
llsi dp[1005][1005], g[1005][1005];
vivi pt[1005];
constexpr llsi NNF = 0x8080808080808080;
void chkmx(llsi &a, llsi b) { if(b > a) a = b; }
void work() {
memset(dp, 0x80, sizeof dp);
memset(g, 0x80, sizeof g);
std::cin >> n;
for(int i = 1; i <= n; ++i) std::cin >> f[i], f[i + n] = f[i];
for(int i = 1; i <= n; ++i) {
std::cin >> pt[i].x >> pt[i].y;
pt[i + n] = pt[i];
}
llsi ans = 0;
for(int len = n - 1; len >= 1; --len) for(int l = 1; l <= 2 * n - len; ++l) {
int r = l + len;
if(f[l] == f[r]) chkmx(dp[l][r], 0);
// std::cerr << "dp[" << l << "][" << r << "] = " << dp[l][r] << char(10);
// std::cerr << "g[" << l << "][" << r << "] = " << g[l][r] << char(10);
chkmx(ans, dp[l][r]);
chkmx(ans, g[l][r]);
if(dp[l][r] >= 0)
for(int k = l + 1; k < r; ++k)
chkmx(g[k][r], dp[l][r] + area(pt[l], pt[r], pt[k]));
if(g[l][r] >= 0)
for(int k = l + 1; k < r; ++k) if(f[l] == f[k])
chkmx(dp[l][k], g[l][r] + area(pt[l], pt[r], pt[k]));
}
std::cout << ans << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
Postscript
这场感觉手速再快一点的话还是有机会 11 题的，不过最后 30min 摆烂有利于避免前几天最后冲刺一个题又没开出来的红温状况，赢！
标签：std,Provincial,Shandong,const,Contest,int,return,include,RI From： https://www.cnblogs.com/cjjsb/p/18446779