Preface
昨天VP的那场没有字符串还没有原形毕露，今天遇到一个后期字符串直接和祁神大眼瞪小眼了
最后一个半小时祁神狂冲F成功写出两个version的假算法，而我已经滚去补之前欠下的题目了
赛后被徐神狠狠拷打了，评价为徐神是我们的红太阳，没有他我们都不能活
A. Orders
签到，按截止时间处理任务即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, k;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n >> k;
map<int, int> mp;
for (int i=1; i<=n; ++i){
int a, b; cin >> a >> b;
// vec.push_back(Node{a, b});
mp[a] += b;
}
bool ok=true;
int cur=0;
for (auto [a, b] : mp){
cur += b;
if (cur > a*k){ok=false; break;}
}
cout << ( ok ? "Yes\n" : "No\n");
}
return 0;
}
B. Building Company
我看完题目人还蒙蔽着，祁神下来看了一眼就会了
考虑任务做了一定不亏，所以就想办法快速维护所有未处理的任务
给每个任务统计一下还有几个维度不满足，用堆来动态更新即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int cnt[N];
struct mes{
int u, id;
bool operator<(const mes &b)const{return u>b.u;}
};
struct Node{
int cur=0;
priority_queue<mes> Q;
};
map<int, Node> mp;
vector<pair<int, int> > vec[N];
int que[N], fr=0, ed=-1;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int g; cin >> g;
for (int i=1; i<=g; ++i){
int t, u; cin>>t>>u;
mp[t].cur=u;
}
int n; cin >> n;
for (int i=1; i<=n; ++i){
int m; cin >> m;
for (int j=1; j<=m; ++j){
int a, b; cin >> a >> b;
Node &nd=mp[a];
if (nd.cur < b) nd.Q.push(mes{b, i}), ++cnt[i];
}
int k; cin >> k;
for (int j=1; j<=k; ++j){
int a, b; cin >> a >> b;
vec[i].emplace_back(a, b);
}
}
for (int i=1; i<=n; ++i) if (0==cnt[i]) que[++ed]=i;
while (fr<=ed){
int x=que[fr++];
for (auto [t, u] : vec[x]){
auto &nd = mp[t];
nd.cur+=u;
while (!nd.Q.empty() && nd.cur>=nd.Q.top().u){
--cnt[nd.Q.top().id];
if (0==cnt[nd.Q.top().id]) que[++ed]=nd.Q.top().id;
nd.Q.pop();
}
}
}
int ans=0;
for (int i=1; i<=n; ++i) if (0==cnt[i]) ++ans;
//for (int i=1; i<=n; ++i) printf("%d ", cnt[i]); puts("");
cout << ans << '\n';
return 0;
}
C. Trie
徐神远程讲出了这题做法的关键，但我是笨比完全策不懂的说
坐等徐神下周补题.png
D. Fast and Fat
思路很好想的一个题，首先最小值最大一眼二分答案，考虑如何检验最小速度为\(v_m\)是否合法
首先可以把人分成两类，一类是\(v_i<v_m\)的，这些人最后一定需要别人来背，可以先都扔进一个multiset里
而另一类人是\(v_j\ge v_m\)的，考虑背人后仍要满足限制，则有\(v_j-(w_i-w_j)\ge v_m\)，即\(w_i\le v_j+w_j-v_m\)
对于这类人我们贪心地在multiset里找一个体重满足限制并且最大的人背上即可，最后看看multiset是否为空
复杂度\(O(n\log^2 n)\)
#include<bits/stdc++.h>
using namespace std;
int t, n;
struct Node{
int v, w;
bool operator<(const Node &b)const{return v<b.v;}
};
vector<Node> vec;
bool check(int vm){
multiset<int> st;
for (auto [v, w] : vec){
if (v<vm){ st.insert(w); continue;}
auto it = st.upper_bound(w+v-vm);
if (it==st.begin()) continue;
--it;
st.erase(it);
}
return st.empty();
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n;
vec.resize(n);
for (int i=0; i<n; ++i) cin >> vec[i].v >> vec[i].w;
sort(vec.begin(), vec.end());
int L=1, R=1e9+5;
while (L<R){
int M=L+(R-L)/2+1;
if (check(M)) L=M;
else R=M-1;
}
cout << L << '\n';
}
return 0;
}
E. Math Problem
因为特判写伪了两人人大眼看了好久
首先不难发现一定是先做完所有的除法再做乘法，否则如果存在相邻的两个操作一乘一除就相互抵消了，一定是劣的
首先特判掉\(k=1\)的情形，接下来我们发现除法的操作次数是\(\log n\)级别的，可以暴枚
同时考虑枚举接下来的乘法操作次数，这个的上界也是\(\log m\)级别的
判断的具体细则就是维护能得到的数的区间\([L,R]\)，每次\(L'=L\times k,R'=R\times k +(k-1)\)
不难发现区间内的所有数都可以被表示出来，因此只要看\([L,R]\)中是否有\(m\)的倍数即可
单组数据复杂度\(O(\log n\times \log m)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18+5;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t, n, k, m, a, b;
cin >> t;
while (t--){
cin >> n >> k >> m >> a >> b;
if (1==k){
if (m==1) cout << 0 << '\n';
else cout << (n%m==0 ? 0 : -1) << '\n';
continue;
}
int ans=INF, res1=0, res2=0;
while (n>=1){
__int128 L=n, R=n;
res2=0;
while ((L-1)/m == R/m){
res2+=a; L*=k; R=R*k+k-1;
}
ans = min(ans, res1+res2);
res1+=b; n/=k;
}
ans = min(ans, res1);
cout << ans << '\n';
}
return 0;
}
F. Colorful Segments
这题祁神比赛时候提出的算法正好是出题人题解中讲的假算法，可以说是被完全预判到了
最后这题交给祁神补了，因此我就不写做法了，具体看官方题解吧
G. Matching
签到题，把所有\(a_i-i\)相同的数放在一起，贪心地每次取出最大的两个匹配即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t, n;
cin >> t;
while (t--){
cin >> n;
map<int, vector<int>> mp;
for (int i=1; i<=n; ++i){
int a; cin >> a;
mp[a-i].push_back(a);
}
int ans=0;
for (auto [v, vec] : mp){
sort(vec.begin(), vec.end(), greater<int>());
for (int i=0; i+1<(int)vec.size(); i+=2){
int res=vec[i]+vec[i+1];
if (res<=0) break;
ans+=res;
}
}
cout << ans << '\n';
}
return 0;
}
H. Be Careful 2
本场放AK题，然而我开场就开到这道题了，看来徐神不在我继承了徐神的被动可还行
I. Three Dice
签到，直接\(6^3\)爆枚即可
#include<bits/stdc++.h>
using namespace std;
bool vis[20][20];
signed main(){
for (int i=1; i<=6; ++i){
for (int j=1; j<=6; ++j){
for (int k=1; k<=6; ++k){
int A=0, B=0;
if (i==1 || i==4) A+=i; else B+=i;
if (j==1 || j==4) A+=j; else B+=j;
if (k==1 || k==4) A+=k; else B+=k;
vis[A][B]=true;
}
}
}
int a, b; cin >> a >> b;
cout << (vis[a][b] ? "Yes\n" : "No\n");
return 0;
}
J. Not Another Path Query Problem
很经典的一个题，看一眼就会做了的程度
发现\(V\)是全局固定的，这就启发我们可以先找出一些前缀，满足当选择的边的权值有这个前缀时就一定满足大于等于\(V\)的条件
这个东西很经典，只要将\(V\)的每一个\(0\)的位置尝试替换成\(1\)，然后保留高位的前缀，这样剩下的低位都可以任意取
最后可以发现只需要处理\(O(\log V)\)级别的前缀，那么我们给每个前缀建一张图然后用并查集维护下连通性即可
总复杂度\(O(m\log V\times \alpha(m))\)
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,m,q,V,x[N],y[N],w[N];
struct DSU
{
int fa[N];
inline void init(CI n)
{
for (RI i=1;i<=n;++i) fa[i]=i;
}
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void merge(CI x,CI y)
{
fa[getfa(x)]=getfa(y);
}
inline bool query(CI x,CI y)
{
return getfa(x)==getfa(y);
}
}D[65];
signed main()
{
//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0);
RI i,j; for (cin>>n>>m>>q>>V,i=1;i<=m;++i) cin>>x[i]>>y[i]>>w[i];
int W=0; vector <int> pre;
for (i=60;i>=0;--i)
{
if ((V>>i)&1LL) { W|=(1LL<<i); continue; }
pre.push_back(W|(1LL<<i));
}
pre.push_back(W); for (i=0;i<pre.size();++i)
{
D[i].init(n); for (j=1;j<=m;++j)
if ((w[j]&pre[i])==pre[i]) D[i].merge(x[j],y[j]);
}
//for (auto x:pre) cout<<x<<endl;
for (i=1;i<=q;++i)
{
int u,v; cin>>u>>v; bool flag=0;
for (j=0;j<pre.size()&&!flag;++j)
if (D[j].query(u,v)) flag=1;
cout<<(flag?"Yes":"No")<<'\n';
}
return 0;
}
K. Difficult Constructive Problem
连着两题遇到这种字典序问题了，但这个题显然比昨天那个要简单好多
首先注意到一个关键性质，当这个字符串的开头和结尾的字符确定后，最后不管怎么填，相邻的不同pair的奇偶性不会改变
因此可以考虑对后缀做一个DP，令\(f_{i,0/1}=(L,R)\)，表示对于从\(i\)开始的后缀，当\(s_i=0/1\)时，后面能凑出的相邻的不同pair的最小值和最大值
不难发现对于某个区间\([L,R]\)，一定有\(L,R\)的奇偶性相同，并且若\(x\in[L,R]\)且\(x\)和\(L,R\)的奇偶性相同，则\(x\)也可以凑出来
有了这个我们就可以很容易地贪心构造答案了，从前往后每一位优先放\(0\)，用上面的DP数组来保证始终能构造出解即可
具体实现的时候细节比较多，需要注意下，同时对于开头和结尾字符没有确定的情况我们直接暴枚一下即可
总复杂度\(O(n)\)，还有注意特判\(n=1\)的情况
#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
struct ifo
{
int l,r;
inline ifo(CI L=INF,CI R=-INF)
{
l=L; r=R;
}
}f[N][2]; int t,n,k; char s[N]; string ans;
inline void solve(void)
{
RI i; f[n][s[n]-'0']=ifo(0,0); f[n][(s[n]-'0')^1]=ifo();
for (i=n-1;i>=1;--i)
{
f[i][0]=f[i][1]=ifo();
auto upt=[&](CI x,CI y)
{
f[x][y]=ifo(min(f[x+1][y].l,f[x+1][y^1].l+1),max(f[x+1][y].r,f[x+1][y^1].r+1));
};
if (s[i]=='?') upt(i,0),upt(i,1); else upt(i,s[i]-'0');
}
if (f[1][s[1]-'0'].l%2!=k%2) return;
if (k<f[1][s[1]-'0'].l||k>f[1][s[1]-'0'].r) return;
string ret=""; ret+=s[1]; int cur=0;
for (i=2;i<n;++i)
{
if (s[i]!='?')
{
cur+=(ret.back()!=s[i]); ret+=s[i]; continue;
}
int tmp=k-(cur+(ret.back()!='0'));
if (tmp%2==f[i+1][0].l%2&&f[i+1][0].l<=tmp&&tmp<=f[i+1][0].r)
{
cur+=(ret.back()!='0'); ret+='0'; continue;
}
if (--tmp,tmp%2==f[i+1][1].l%2&&f[i+1][1].l<=tmp&&tmp<=f[i+1][1].r)
{
cur+=(ret.back()!='0'); ret+='0'; continue;
}
tmp=k-(cur+(ret.back()!='1'));
if (tmp%2==f[i+1][1].l%2&&f[i+1][1].l<=tmp&&tmp<=f[i+1][1].r)
{
cur+=(ret.back()!='1'); ret+='1'; continue;
}
if (--tmp,tmp%2==f[i+1][0].l%2&&f[i+1][0].l<=tmp&&tmp<=f[i+1][0].r)
{
cur+=(ret.back()!='1'); ret+='1'; continue;
}
return;
}
ret+=s[n]; ans=min(ans,ret);
}
int main()
{
//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d%s",&n,&k,s+1); ans="2";
if (n==1)
{
if (k) puts("Impossible"); else
{
if (s[1]=='?') s[1]='0';
putchar(s[1]); putchar('\n');
}
continue;
}
if (s[1]=='?'&&s[n]=='?')
{
s[1]='0'; s[n]='0'; solve();
s[1]='0'; s[n]='1'; solve();
s[1]='1'; s[n]='0'; solve();
s[1]='1'; s[n]='1'; solve();
} else if (s[1]=='?')
{
s[1]='0'; solve(); s[1]='1'; solve();
} else if (s[n]=='?')
{
s[n]='0'; solve(); s[n]='1'; solve();
} else solve();
if (ans=="2") puts("Impossible"); else
{
for (RI i=0;i<ans.size();++i) putchar(ans[i]); putchar('\n');
}
}
return 0;
}
L. Puzzle: Sashigane
小清新构造题
考虑我们初始时有一个\(1\times 1\)的正方形，我们考虑每一步把它的边长扩大\(1\)，这样只要贴着原来的正方形放一个两边等长的L形即可
不难发现每次至少存在一个方向扩展后是合法的，因此没有无解的情况
写的时候需要搞清楚题目中输出的规则，因此这题就没有讲给祁神写而是自己爬上去搓了下
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,xL,xR,yL,yR,vis[N][N];
inline bool check(CI r,CI c,CI h,CI w)
{
if (r<1||r>n||c<1||c>n) return 0;
if (h>0)
{
for (RI i=0;i<=h;++i) if (r+i<1||r+i>n||vis[r+i][c]) return 0;
} else
{
for (RI i=h;i<=0;++i) if (r+i<1||r+i>n||vis[r+i][c]) return 0;
}
if (w>0)
{
for (RI i=0;i<=w;++i) if (c+i<1||c+i>n||vis[r][c+i]) return 0;
} else
{
for (RI i=w;i<=0;++i) if (c+i<1||c+i>n||vis[r][c+i]) return 0;
}
return 1;
}
inline void paint(CI r,CI c,CI h,CI w)
{
printf("%d %d %d %d\n",r,c,h,w);
if (h>0)
{
for (RI i=0;i<=h;++i) vis[r+i][c]=1;
} else
{
for (RI i=h;i<=0;++i) vis[r+i][c]=1;
}
if (w>0)
{
for (RI i=0;i<=w;++i) vis[r][c+i]=1;
} else
{
for (RI i=w;i<=0;++i) vis[r][c+i]=1;
}
}
int main()
{
//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
scanf("%d%d%d",&n,&xL,&yL); xR=xL; yR=yL; vis[xL][yL]=1;
puts("Yes"); printf("%d\n",n-1);
for (RI len=1;len<n;++len)
{
if (check(xL-1,yL-1,len,len)) { paint(--xL,--yL,len,len); continue; }
if (check(xR+1,yL-1,-len,len)) { paint(++xR,--yL,-len,len); continue; }
if (check(xL-1,yR+1,len,-len)) { paint(--xL,++yR,len,-len); continue; }
if (check(xR+1,yR+1,-len,-len)) { paint(++xR,++yR,-len,-len); continue; }
}
return 0;
}
M. Computational Geometry
好久没遇到计算几何了，但是无所谓祁神还是一样秒
这题其实很简单只要枚举固定的两个点的位置，中间部分的面积用前缀和算一下
而剩下一个点的最优选择很显然可以三分，然后这题就做完了
总复杂度\(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int t, n, k;
struct Pt{
int x, y;
int crs(Pt b){return x*b.y-y*b.x;}
Pt operator-(const Pt b)const{return Pt{x-b.x, y-b.y};}
}pt[N*2];
__int128 pre[N*2];
int dis(Pt p, Pt a, Pt b){
return abs((p-a).crs(b-a));
}
int bina(int l, int r){
int L=l+1, R=r-1;
while (L<R){
int M1 = L+(R-L)/2;
int M2 = M1 + 1;
// printf("M1=%d M2=%d\n", M1, M2);
if (dis(pt[M1], pt[l], pt[r])>dis(pt[M2], pt[l], pt[r])) R=M2-1;
else L=M1+1;
}
return L;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n >> k;
for (int i=0; i<n; ++i){
cin >> pt[i].x >> pt[i].y;
pt[n+i]=pt[i];
}
pt[n*2]=pt[0];
for (int i=1; i<=n; ++i) pre[i]=pre[n+i]=pt[i-1].crs(pt[i]);
for (int i=1; i<=n*2; ++i) pre[i]+=pre[i-1];
__int128 ans=0;
for (int i=0; i<n; ++i){
__int128 sum1=pre[i+k]-pre[i] + pt[i+k].crs(pt[i]);
int id=bina(i+k, i+n);
sum1 += (pt[i+n]-pt[id]).crs(pt[i+k]-pt[id]);
// printf("i=%d sum=%d\n", i, sum1);
ans=max(ans, sum1);
}
if (ans%2==1) cout << (int)(ans/2) << ".5\n";
else cout << (int)(ans/2) << '\n';
}
return 0;
}
Postscript
希望徐神的CPU能早日搓好，赶紧回来带飞我们吧
标签：Provincial,Shandong,return,Contest,int,CI,cin,vec,include From： https://www.cnblogs.com/cjjsb/p/17873383.html