Preface
VP到自己学校出的题了可海星，不得不说学长们出的题比起昨天VP的CCPC2022广州做起来要舒服地多
这场前面写题都很顺基本都是一发过，中期的medium也没怎么卡思路和卡机子，一道一道地慢慢出
最后一个小时徐神RushF可惜没Rush出来，然后我和祁神坐在下面把B的做法给搞出来了，但不知道复杂度是否正确因此就没敢去写
总之很好的一套题，爱来自电专
A. Dunai
yysy这题题目真难读啊，开场看了半天才看懂的说
不难发现可以把某个位置的冠军选手个数和普通选手个数分别统计出来
考虑一个队伍的配置可以有\(k=1,2,3,4,5\)个冠军选手，那么不妨贪心地先组冠军选手较少的队
直接\(2^5\)枚举所有可能的方案即可
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=10;
int n,m,x,c[N],p[N],ans; string s; map <string,int> cp;
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
RI i,j; for (cin>>n,i=1;i<=n;++i)
for (j=1;j<=5;++j) cin>>s,cp[s]=j;
for (cin>>m,i=1;i<=m;++i)
{
cin>>s>>x;
if (cp.count(s)) ++c[cp[s]-1]; else ++p[x-1];
}
vector <int> st; for (i=1;i<(1<<5);++i) st.push_back(i);
auto cmp=[&](CI x,CI y)
{
return __builtin_popcount(x)<__builtin_popcount(y);
};
sort(st.begin(),st.end(),cmp);
for (auto x:st)
{
int mi=1e9; for (i=0;i<5;++i)
if ((x>>i)&1) mi=min(mi,c[i]); else mi=min(mi,p[i]);
ans+=mi; for (i=0;i<5;++i)
if ((x>>i)&1) c[i]-=mi; else p[i]-=mi;
}
return printf("%d",ans),0;
}
B. Recruitment
感觉我们学校的题很喜欢出这种状态数乍看很多实则很少的搜索题，今年的校赛有道题好像也是这样
这题首先要注意到因为最后的\(s_i\le 10^9\)，因此有效的乘法操作是很少的，绝大多数的操作都是把\(x+1\)改成\(x\times 1\)
我们可以特判掉这种操作，那么剩下的有效的操作次数就大约只有\(30\)次了
考虑将\(x+y\)变成\(x\times y\)，会将整个序列的值增加\((x-1)\times (y-1)-1\)，而由于我们已经知道了\(x\times y\)的值，因此可以直接大力分解约数来判断划分方案
剩下的就是复杂度分析了，根据Tutorial中的说法有效的状态总数很少，因此可以直接大力BFS出解
这里我写的时候放飞自我了直接把所有状态都用一个pair <vector <int>,int>来表示了，前面一个表示有效的操作带来的序列，后面一个表示特判的\(1\)的个数
最后跑了1500+ms勉强通过，估计优化下STL部分会快很多
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef vector <int> VI;
typedef pair <VI,int> ifo;
const int N=100005;
int n,s[N]; map <ifo,ifo> pre; queue <ifo> q;
int main()
{
//("B.in","r",stdin); freopen("B.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&s[i]);
for (i=1;i<n;++i) if (s[i]-1>s[i+1]) return puts("-1"),0;
VI st; st.push_back(s[n]); q.push(mp(st,0)); ifo end;
while (!q.empty())
{
auto [seq,num]=q.front(); q.pop();
int step=seq.size()+num;
if (step==n) { end=mp(seq,num); break; }
int dlt=s[n-step+1]-s[n-step];
if (dlt==-1)
{
ifo nxt=mp(seq,num+1);
if (!pre.count(nxt)) pre[nxt]=mp(seq,num),q.push(nxt);
continue;
}
for (i=0;i<seq.size();++i)
{
for (RI x=1;x*x<=seq[i];++x) if (seq[i]%x==0)
{
int y=seq[i]/x; if (1+dlt!=1LL*(x-1)*(y-1)) continue;
VI ns; for (j=0;j<i;++j) ns.push_back(seq[j]);
ns.push_back(x); ns.push_back(y);
for (j=i+1;j<seq.size();++j) ns.push_back(seq[j]);
ifo nxt=mp(ns,num);
if (!pre.count(nxt)) pre[nxt]=mp(seq,num),q.push(nxt);
}
}
}
if (end.fi.size()+end.se!=n) return puts("-1"),0;
for (auto x:end.fi) printf("%d ",x);
for (i=1;i<=end.se;++i) printf("%d ",1); putchar('\n');
VI op; for (i=1;i<end.fi.size();++i) op.push_back(i);
int lst=end.fi.size(); for (i=1;i<n;++i)
{
ifo nxt=pre[end];
if (end.se!=nxt.se) { printf("%d\n",lst++); end=nxt; continue; }
for (j=0;j<op.size();++j)
if (end.fi[j]*end.fi[j+1]==nxt.fi[j])
{
printf("%d\n",op[j]); op.erase(op.begin()+j); break;
}
end=nxt;
}
return 0;
}
C. Grass
小清新几何题
首先发现无解的情形只有\(n<5\)以及所有点共线的情况
否则不难发现对于任意\(5\)个不共线的点，其中至少存在一个点作为中间的那个点，感性一下很好理解，具体证明的话可以去看Tutorial
当时比赛的时候本来还打算写个随机化的来着，后面发现有些队也是拿随机化跑过去的，比较有趣
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Pt{
int x, y;
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
int crs(Pt b)const{return x*b.y-y*b.x;}
int quad(){
if (x>0&&y>=0) return 1; if (x<=0&&y>0) return 2;
if (x<0&&y<=0) return 3; if (x>=0&&y<0) return 4;
return -1;
}
};
struct Node{
Pt v;
int qd;
bool operator<(const Node &b)const{
return qd!=b.qd ? qd < b.qd : v.crs(b.v)>0;
}
};
const int N = 1e5+5;
int t, n;
bool line(vector<Pt> &vec){
int sz=vec.size();
Pt v = vec[1]-vec[0];
for (int i=2; i<sz; ++i){
if (v.crs(vec[i]-vec[0])!=0) return false;
}
return true;
}
bool findA(vector<Pt> &vec){
for (int i=0; i<5; ++i){
set<Node> st;
for (int j=0; j<5; ++j){
if (i==j) continue;
Pt v = vec[j]-vec[i];
st.insert(Node{v, v.quad()});
}
// printf("i=%d sz=%d\n", i, st.size());
if (st.size()==4){
swap(vec[0], vec[i]);
return true;
}
}
return false;
}
signed main(){
scanf("%lld", &t);
while (t--){
scanf("%lld", &n);
vector<Pt> vec(n);
for (int i=0; i<n; ++i) scanf("%lld%lld", &vec[i].x, &vec[i].y);
if (n<5 || line(vec)){
puts("NO");
continue;
}
vector<Pt> ans;
for (int i=0; i<4; ++i) ans.push_back(vec[i]);
for (int i=4; i<n; ++i){
ans.push_back(vec[i]);
if (!line(ans)){
findA(ans);
break;
}
ans.pop_back();
}
puts("YES");
for (int i=0; i<5; ++i){
printf("%lld %lld\n", ans[i].x, ans[i].y);
}
}
return 0;
}
D. Sternhalma
很一眼的状压题，但难点在于转移时状态的变化如何实现
比赛的时候我们队想了种很高明的做法，将图中的点从上到下从左到右编号\(0\sim 18\)
然后运用人类智慧直接在下机的时候手动把每个点的合法转移写出来，即它通过踩哪个格子跳到了哪个格子
有了这个后这道题就变成一个非常傻逼的题了，复杂度约为\(O(2^{19}\times 19\times 6)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=20;
int a[N],t,f[(1<<N)+5],vis[(1<<N)+5];
auto v = vector<vector<pi> > {
vector<pi> { { 1, 2}, { 3, 7}, { 4, 9} },
vector<pi> { { 4, 8}, { 5, 10} },
vector<pi> { { 1, 0}, { 5, 9}, { 6, 11} },
vector<pi> { { 4, 5}, { 8, 13} },
vector<pi> { { 8, 12}, { 5, 6}, { 9, 14} },
vector<pi> { { 4, 3}, { 9, 13}, {10, 15} },
vector<pi> { { 5, 4}, {10, 14} },
vector<pi> { { 3, 0}, { 8, 9}, {12, 16} },
vector<pi> { { 4, 1}, { 9, 10}, {13, 17} },
vector<pi> { { 8, 7}, { 4, 0}, { 5, 2}, {10, 11}, {14, 18}, {13, 16} },
vector<pi> { { 9, 8}, { 5, 1}, {14, 17} },
vector<pi> { { 6, 2}, {10, 9}, {15, 18} },
vector<pi> { { 8, 4}, {13, 14} },
vector<pi> { { 8, 3}, { 9, 5}, {14, 15} },
vector<pi> { {13, 12}, { 9, 4}, {10, 6} },
vector<pi> { {10, 5}, {14, 13} },
vector<pi> { {12, 7}, {13, 9}, {17, 18} },
vector<pi> { {13, 8}, {14, 10} },
vector<pi> { {17, 16}, {14, 9}, {15, 11} },
};
inline int DP(CI st)
{
if (st==0) return 0; if (vis[st]) return f[st]; vis[st]=1;
int ret=0; for (RI i=0;i<19;++i) if ((st>>i)&1)
{
ret=max(ret,DP(st^(1<<i)));
for (auto [x,y]:v[i]) if (((st>>x)&1)&&!((st>>y)&1))
ret=max(ret,DP(st^(1<<i)^(1<<x)^(1<<y))+a[x]);
}
return f[st]=ret;
}
int main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
RI i; for (i=0;i<19;++i) scanf("%d",&a[i]);
for (scanf("%d",&t);t;--t)
{
int cur=0; for (i=0;i<19;++i)
{
char ch; while (ch=getchar(),ch!='.'&&ch!='#');
if (ch=='#') cur|=(1<<i);
}
printf("%d\n",DP(cur));
}
return 0;
}
E. Python Will be Faster than C++
签到题，不难发现其实最后后面的部分一定成等差数列，但由于这题数据范围很小因此可以直接暴力模拟
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,k,a[N];
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
if (a[n-1]<=a[n]) return puts("Python will never be faster than C++"),0;
for (i=n+1;;++i) if (a[i]=max(0,2*a[i-1]-a[i-2]),a[i]<k) break;
return printf("Python 3.%d will be faster than C++",i),0;
}
F. Mooncake Delivery
这题比赛的时候徐神已经基本想出来了，因为每当走到一个点时我们可以把前面走的所有颜色和它不同的点的树全部砍了
因此这题的答案形式就是“每一段的点权和 加上下一段的第一个顶点的点权”的最大值
考虑先把同色的连通块内部两两点间的最短路用Floyd跑出来，然后通过枚举每段的起点，终点，下一段的起点来建出一张新的有向带权图
最后要求以每个点为起点出发的有向最小瓶颈路，那么直接跑\(n\)次Prim即可
总复杂度\(O(n^3)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
#define int llsi
constexpr int $n = 301;
int T, n, m, c[$n], edge[$n][$n], vis[$n];
llsi w[$n], dp1[$n][$n], dp2[$n][$n], a1[$n], a2[$n], mn[$n];
inline void upd(llsi &a, llsi b) {
if(b < a) a = b;
}
int32_t main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> T; while(T--) {
std::cin >> n >> m;
memset(edge, 0, sizeof edge);
memset(dp1, 0x1f, sizeof dp1);
memset(dp2, 0x1f, sizeof dp2);
for(int i = 1; i <= n; ++i) std::cin >> c[i];
for(int i = 1; i <= n; ++i) std::cin >> w[i];
for(int i = 1, a, b; i <= m; ++i) {
std::cin >> a >> b;
edge[a][b] = edge[b][a] = 1;
if(c[a] == c[b])
dp1[a][b] = dp1[b][a] = w[a] + w[b];
}
for(int i = 1; i <= n; ++i) dp1[i][i] = w[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) if(c[j] == c[i])
for(int k = 1; k <= n; ++k) if(c[k] == c[j])
upd(dp1[j][k], dp1[j][i] + dp1[i][k] - w[i]),
upd(dp1[k][j], dp1[k][i] + dp1[i][j] - w[i]);
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i) if(c[i] == c[k])
for(int j = 1; j <= n; ++j) if(c[k] != c[j] && edge[k][j])
upd(dp2[i][j], dp1[i][k] + w[j]);
// for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j)
// std::cerr << dp1[i][j] << char(j == n ? 10 : 32);
for(int i = 1; i <= n; ++i) {
memset(mn + 1, 0x1f, sizeof(llsi) * n);
memset(vis + 1, 0, sizeof(int) * n);
memset(a1 + 1, 0x1f, sizeof(llsi) * n);
memset(a2 + 1, 0x1f, sizeof(llsi) * n);
a1[i] = mn[i] = 0;
for(int YY = 1; YY <= n; ++YY) {
llsi minp = -1, minv = 3e18;
for(int j = 1; j <= n; ++j) if(!vis[j] && mn[j] < minv)
minv = mn[j], minp = j;
if(minp == -1) break;
int fd = minp;
vis[fd] = 1;
for(int j = 1; j <= n; ++j)
if(!vis[j] && dp2[fd][j] < mn[j])
mn[j] = dp2[fd][j], a1[j] = std::max(a1[fd], mn[j]);
}
for(int j = 1; j <= n; ++j) for(int k = 1; k <= n; ++k) if(c[j] == c[k])
upd(a2[k], std::max(a1[j], dp1[j][k]));
for(int j = 1; j <= n; ++j) std::cout << std::min(a1[j], a2[j]) << char(j == n ? 10 : 32);
}
// std::cerr << "----------\n";
}
return 0;
}
G. Grade 2
这题上来队友跟我说有个反演题，我上来一波操作发现这题反演并没有什么卵用
但后面没啥思路了徐神就上去打了个表，后面发现好像是有循环节的
然后我站在后面突然意识到这个东西有个很trivial的循环节就是\(2^{\lceil\log{x}\rceil}\)，因为当\(k=2^{\lceil\log{x}\rceil}\)时后面\(\lceil\log{x}\rceil\)都是\(0\)，因此和\(k=0\)是等价的
因此直接暴力把一个循环节内的所有数算出来后就可以\(O(1)\)计算答案了
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=4e6+5;
int x,n,l,r,T,pfx[N];
inline int calc(CI x)
{
return x/T*pfx[T-1]+pfx[x%T];
}
signed main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
RI i; for (scanf("%lld%lld",&x,&n),T=1;T<x;T<<=1);
for (i=0;i<T;++i) pfx[i]=pfx[i-1]+(__gcd((i*x)^x,x)==1);
while (n--) scanf("%lld%lld",&l,&r),printf("%lld\n",calc(r)-calc(l-1));
return 0;
}
H. Party Animals
防AK题，做不了一点
I. Dragon Bloodline
很典的二分+贪心题，难点在于现场摸索nth_element的用法
首先不难发现答案具有二分性，不妨设最后能得到\(M\)个蛋，则可以设\(c_i=a_i\times M\)，现在就是要把每个\(c_i\)都减小到小于等于\(0\)
不难发现可以从大到小枚举每种等级\(j\)的龙，首先尽量地使得它们都能被完全地用上
现在问题是如果不存在\(c_i\ge 2^{j-1}\)而\(b_j\)还有剩余，那么久在剩下的\(c_i\)中挑最大的\(b_j\)个删掉即可
本来打算用sort来实现的，但后面问了嘴徐神发现有nth_element这个好东西，这下复杂度直接降了个\(\log\)
还要注意由于最后答案的值域是\(10^{17}\)的，再乘上\(10^9\)的话就会爆long long，因此要开__int128
总复杂度\(O(n\log n\log a_i)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef __int128 i128;
const int N=50005;
int t,n,k,a[N],b[N],tb[N];
inline bool check(CI M)
{
RI i; vector <i128> t; for (i=1;i<=k;++i) b[i]=tb[i];
for (i=1;i<=n;++i) t.push_back(i128(a[i])*M);
for (i=k;i>=1;--i)
{
vector <i128> nt; int c=1LL<<i-1;
for (auto x:t)
{
int d=min(x/c,i128(b[i])); b[i]-=d; x-=c*d;
if (x>0) nt.push_back(x);
}
if (b[i]>0)
{
if (nt.size()<=b[i]) nt.clear(); else
{
nth_element(nt.begin(),nt.begin()+b[i]-1,nt.end(),greater <i128>());
nt=vector <i128>(nt.begin()+b[i],nt.end());
}
}
t=nt;
}
return t.empty();
}
signed main()
{
//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (i=1;i<=k;++i) scanf("%lld",&tb[i]);
int l=0,r=1e17,mid,ret; while (l<=r)
if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
printf("%lld\n",ret);
}
return 0;
}
J. Eat, Sleep, Repeat
这题徐神写的，好像过的人挺多的就不管了，但感觉细节好像挺多的来着
#include <bits/stdc++.h>
using llsi = long long signed int;
template<typename T1, typename T2>
llsi solve(T1 abeg, T1 aend, T2 lbeg, T2 lend) {
llsi res = 0, gg = 0;
// std::cerr << "debug :\n";
// for(T1 i = abeg; i < aend; ++i) std::cerr << *i << char(i == aend - 1 ? 10 : 32);
// for(T2 i = lbeg; i < lend; ++i) std::cerr << '[' << i->first << ' ' << i->second << ']' << char(i == lend - 1 ? 10 : 32);
for(T1 i = abeg; i < aend; ++i) res += *i;
int n = aend - abeg;
int ug = lbeg->first;
for(T2 i = lbeg; i < lend; ++i, ug += 1) {
int mn;
if(ug == i->first) mn = std::min(n, i->second);
else mn = n;
gg += ug * mn;
n -= mn;
}
if(n) gg += ug * n;
// std::cerr << res << ' ' << gg << '\n';
return res - gg;
}
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
int T; std::cin >> T;
while(T--) {
int n, k;
std::cin >> n >> k;
llsi asum = 0;
std::vector<int> a(n);
std::vector<std::pair<int, int> > li(k);
for(auto &a: a) std::cin >> a;
for(auto &[x, y]: li) std::cin >> x >> y;
li.push_back({-1, 0});
li.push_back({1e9 + 7, 0});
std::sort(a.begin(), a.end());
std::sort(li.begin(), li.end());
auto ap = a.begin();
auto lp = li.begin();
while(ap != a.end()) {
auto al = ap; auto ll = lp;
while(lp->second || lp->first < *ap) {
if(lp->second == 0) ll = lp;
lp += 1;
}
while(ap != a.end() && *ap < lp->first) ap += 1;
asum += solve(al, ap, ll, lp);
}
std::cout << (asum & 1 ? "Pico\n" : "FuuFuu\n");
}
return 0;
}
K. I Wanna Maker
很有意思的一个题，WA了两发后发现是无解和无限解的判断顺序出了点问题
首先这题有个关键结论，对于区间\([l,r]\)以及给定的\(k,x\)，若\(x\)可以被区间表示出的话则一定有：
\[\frac{(2l+k-1)\times k}{2}\le x\le \frac{(2r-k+1)\times k}{2}
\]
选出区间中最小的\(k\)个数作为下界，最大的\(k\)个数作为上界，则位于上下界之间的所有数都可以被表示出来
有了这个后对于第一种类型的限制，我们可以写成：
\[l\le \min(\lfloor\frac{2x+k\times (1-k)}{2k}\rfloor,0)\\
r\ge \lceil\frac{2x+k\times(k-1)}{2k}\rceil
\]
不妨把\(l\)看作坐标系中的横轴，\(r\)看作纵轴，则一条限制代表着某个矩形区域
而同理，一条第二种类型的限制可以看成排除某个矩形区域后的区域
不难发现将第一种操作的矩形区域求交，第二种操作的矩形区域求并后再求最后的合法区域中的整点个数即可
前者很好处理，后者观察后可以发现能把所有限制点按照横坐标排序后用单调栈维护纵坐标也递增的阶梯状区域，最后求答案的话手玩一下就很容易了
总复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef long double LDB;
typedef pair <int,int> pi;
const int N=100005;
int t,n,m,tp,k,x,sx,sy,top; pi p[N],stk[N];
signed main()
{
//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%lld",&n),sx=sy=-1,m=0,i=1;i<=n;++i)
{
scanf("%lld%lld%lld",&tp,&k,&x);
int l=max(0LL,(2LL*x+k*(1-k))/(2LL*k)),r=(2LL*x+k*(k-1)+2LL*k-1)/(2LL*k);
if (tp==1)
{
if (sx==-1) sx=l,sy=r; else sx=min(sx,l),sy=max(sy,r);
} else p[++m]=pi(l,r);
}
if (sx==0) { puts("0"); continue; }
if (sx==-1||m==0) { puts("-1"); continue; }
for (sort(p+1,p+m+1),stk[top=0]=pi(0,0),i=1;i<=m;++i)
{
while (top&&stk[top].se>=p[i].se) --top;
stk[++top]=p[i];
}
if (sx>stk[top].fi) { puts("-1"); continue; }
int ans=0; for (i=1;i<=top;++i)
{
if (sx<=stk[i-1].fi||stk[i].se<=sy) continue;
ans+=(sx-stk[i-1].fi)*(stk[i].se-sy); sy=stk[i].se;
}
printf("%lld\n",ans);
}
return 0;
}
L. Novice Magician
题目都没看，一眼做不来
M. String Master
徐神思考了很久，得出了很多有效结论，但因为要很多的分类讨论啥的后面就弃疗了
Postscript
连训三天有点吃力了的说，明天小休一天后天开始还有学校组织的四天联训的说
- Programming Collegiate Contest Weihai Chinaprogramming collegiate contest weihai programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate contest harbin programming collegiate codeforces contest