Preface
下下周还要去打重庆市赛,最近就找些省赛来练练手
不得不说省赛的签到题是真的多,人均10+的过题看起来还是很恐怖的
这场虽然因为徐神缺席,而且前面的题目都让祁神来写导致罚时略高,但无所谓反正最后也摸到了11题(主要是没有字符串)
A. Chuanpai
某不知题意的签到
#include<bits/stdc++.h>
int ans[13]={0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1};
int main(){
int t; scanf("%d", &t);
while (t--){
int n; scanf("%d", &n);
if (n<=12) printf("%d\n", ans[n]);
else printf("0\n");
}
return 0;
}
B. Hotpot
注意到经过\(2n\)轮后锅一定是空的,因此可以先模拟一遍\(2n\)轮的情况,再模拟剩下的情况
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int t, n, k, m, A[N], ans[N];
bool vis[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n >> k >> m;
for (int i=0; i<n; ++i) cin >> A[i];
for (int i=0; i<n; ++i) ans[i]=0;
for (int i=1; i<=k; ++i) vis[i]=false;
for (int i=0; i<2*n; ++i){
if (!vis[A[i%n]]) vis[A[i%n]]=true;
else vis[A[i%n]]=false, ++ans[i%n];
}
for (int i=0; i<n; ++i) ans[i]*=(m/(2*n));
for (int i=0; i<m%(2*n); ++i){
if (!vis[A[i%n]]) vis[A[i%n]]=true;
else vis[A[i%n]]=false, ++ans[i%n];
}
for (int i=0; i<n; ++i) cout << ans[i] << (i==n-1 ? '\n' : ' ');
}
return 0;
}
C. Triangle Pendant
刚体力学,启动
祁神比赛时候推出了三根绳子都绷直的情况,结果后面发现还有一根/两根绳子绷直的情况,直接寄
D. Rock Paper Scissors
不难发现后手的策略一定是,当知道了先手出的牌后,优先出能赢的牌,若没有就出打平的牌,否则只能输了
而先手的策略一定是选择出某种牌之后直接把这种牌出完,因此可以全排列枚举先手的策略然后模拟算一遍即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int t; scanf("%lld", &t);
while (t--){
int b[3], d[3], tmp1[3], tmp2[3];
for (int i=0; i<3; ++i) scanf("%lld", &b[i]);
for (int i=0; i<3; ++i) scanf("%lld", &d[i]);
int ans=1e18;
for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) for (int k=0; k<3; ++k){
if (i==j || i==k || j==k) continue;
int tans=0;
memcpy(tmp1, b, sizeof(b));
memcpy(tmp2, d, sizeof(d));
int cur=(i+1)%3;
while (tmp1[i]>0){
int res=min(tmp1[i], tmp2[cur]);
tmp1[i]-=res; tmp2[cur]-=res;
if (cur==(i+1)%3) tans+=res;
if (cur==(i-1+3)%3) tans-=res;
--cur; if (cur<0) cur+=3;
}
// printf("i=%d tans=%d\n", i, tans);
cur=(j+1)%3;
while (tmp1[j]>0){
int res=min(tmp1[j], tmp2[cur]);
tmp1[j]-=res; tmp2[cur]-=res;
if (cur==(j+1)%3) tans+=res;
if (cur==(j-1+3)%3) tans-=res;
--cur; if (cur<0) cur+=3;
}
// printf("j=%d tans=%d\n", j, tans);
cur=(k+1)%3;
while (tmp1[k]>0){
int res=min(tmp1[k], tmp2[cur]);
tmp1[k]-=res; tmp2[cur]-=res;
if (cur==(k+1)%3) tans+=res;
if (cur==(k-1+3)%3) tans-=res;
--cur; if (cur<0) cur+=3;
}
// printf("k=%d tans=%d\n", k, tans);
ans = min(ans, tans);
}
printf("%lld\n", ans);
}
return 0;
}
E. Don’t Really Like How The Story Ends
寄了一个小时才发现没判重边,我还以为做法假了
不难发现可以贪心构造,考虑已经处理了前\(i\)个点,现在要尝试把\(i+1\)加进来
按照DFS序找到最靠近栈顶,且还有未访问邻居的点\(x\),若\(x\)和\(i+1\)有边则直接加入\(i+1\),否则必须新加入一条\(x\)和\(i+1\)的边
不难发现用这种方法构造出的答案一定是最小的
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int t, n, m;
set<int> st[N];
int stk[N], top=-1;
int deg[N];
signed main(){
//freopen("1.in", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
for (int i=1; i<=n; ++i) st[i].clear();
memset(deg, 0, (n+1)*sizeof(int));
for (int i=1; i<=m; ++i){
int u, v; cin >> u >> v;
if (u==v) continue;
if (st[u].count(v)) continue;
st[u].insert(v); st[v].insert(u);
++deg[u]; ++deg[v];
}
int ans=0;
top=-1; stk[++top]=1;
for (int i=2; i<=n; ++i){
while (top>0 && deg[stk[top]]<=0) --top;
if (0==st[stk[top]].count(i)){
++ans;
// printf("u=%d v=%d\n", stk[top], i);
}
for (int v : st[i]){
if (v<i) --deg[v], --deg[i];
}
stk[++top]=i;
}
cout << ans << '\n';
}
return 0;
}
F. Direction Setting
一眼网络流傻逼题
考虑把边看成左边的一排点,原图中的点看作右边的一排点
对于左边的点,从源点向其连容量为\(1\)的边;而右边的点向汇点连容量为\(a_i\)的边
对于每条边的两个端点\(x_i,y_i\),将其向右边对应的点各连容量为\(1\)的边即可
最后的答案就是\(m\)减去最大流,方案也很好求
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=305;
int T,n,m,x[N],y[N];
namespace Network_Flow
{
const int NN=1005,MM=1e6+5,INF=1e9;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t; queue <int> q;
inline void clear(void)
{
for (RI i=1;i<=t;++i) head[i]=0; cnt=1;
}
inline void addedge(CI x,CI y,CI z)
{
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,t+1<<2); dep[s]=1; q=queue <int>(); q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=0; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,t+1<<2),ret+=DFS(s,t,INF); return ret;
}
inline void solve(void)
{
for (RI i=1,j;i<=m;++i)
{
bool flag=0; for (j=head[i];j;j=e[j].nxt)
if (e[j].to!=s&&!e[j].v) putchar(e[j].to-m==x[i]?'1':'0'),flag=1;
if (!flag) putchar('0');
}
putchar('\n');
}
};
using namespace Network_Flow;
int main()
{
//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
for (scanf("%d",&T);T;--T)
{
RI i; int a; for (scanf("%d%d",&n,&m),s=n+m+1,t=s+1,i=1;i<=n;++i) scanf("%d",&a),addedge(m+i,t,a);
for (i=1;i<=m;++i) scanf("%d%d",&x[i],&y[i]),addedge(s,i,1),addedge(i,m+x[i],1),addedge(i,m+y[i],1);
printf("%d\n",m-Dinic()); solve(); clear();
}
return 0;
}
G. Hourly Coding Problem
说实话没太看懂题解在讲什么,到vjudge上找了各代码一看300行直接不想补了
H. Nihongo wa Muzukashii Desu
签到题,但是有人自作聪明忘了行く的特殊变形我不说是谁(样例没过也能交是真高手)
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int n;
int main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>n;n;--n)
{
string s; cin>>s; if (s=="ikimasu")
{
cout<<"itte"<<endl; continue;
}
reverse(s.begin(),s.end());
if (s.size()>=7&&s[5]=='h'&&s[6]=='s')
{
string t=s.substr(7); reverse(t.begin(),t.end());
t+="shite"; cout<<t<<endl;
} else
if (s.size()>=6&&s[5]=='g')
{
string t=s.substr(6); reverse(t.begin(),t.end());
t+="ide"; cout<<t<<endl;
} else
if (s.size()>=6&&s[5]=='k')
{
string t=s.substr(6); reverse(t.begin(),t.end());
t+="ite"; cout<<t<<endl;
} else
if (s.size()>=6&&s[5]=='m'||s[5]=='b'||s[5]=='n')
{
string t=s.substr(6); reverse(t.begin(),t.end());
t+="nde"; cout<<t<<endl;
} else
if (s.size()>=7&&s[5]=='h'&&s[6]=='c')
{
string t=s.substr(7); reverse(t.begin(),t.end());
t+="tte"; cout<<t<<endl;
} else
if (s.size()>=6&&s[5]=='r')
{
string t=s.substr(6); reverse(t.begin(),t.end());
t+="tte"; cout<<t<<endl;
}
}
return 0;
}
I. Monster Hunter
挺有意思的一个题,猜了猜结论也艹过去了
首先一眼想到二分答案,这样check
的话就只用考虑用已知数量的\(1,2,3\)来干掉所有怪兽了
考虑如果只有\(1,2\)的话就是各很典的贪心,先尽量用\(2\),如果所有数都被干到\(1\)后还有剩下的\(2\)就接着干,然后再用剩下的\(1\)
而加入\(3\)后我们考虑先把\(3\)用完,然后套上面的贪心,经过一些手玩我们可以发现:
- 当某个怪物的血量为大于等于\(3\)的奇数时,可以用一个\(3\)去干它
- 当某个怪物的血量为大于等于\(6\)的偶数时,可以用两个\(3\)去干它
但要注意我们要尽量多的留下偶数,因为这样可以尽量优化\(2\)的使用,因此要优先处理第一种情况再考虑第二种情况
然后如果还有多余的\(3\),直接优先干剩余的较大的数即可,然后再套上面的贪心即可
总复杂度\(O(n\log (m\times a_i))\)
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],m,h[N],c[5];
inline bool check(CI lim)
{
RI i; static int tc[5],th[N];
for (i=1;i<=3;++i) tc[i]=c[i]*(lim/n);
for (i=1;i<=lim%n;++i) ++tc[a[i]];
for (i=1;i<=m;++i) th[i]=h[i];
for (i=1;i<=m&&tc[3]>0;++i)
if (th[i]>=3&&th[i]%2==1) --tc[3],th[i]-=3;
for (i=1;i<=m&&tc[3]>0;++i)
if (th[i]>=6&&th[i]%2==0)
{
int dlt=min(tc[3]/2,th[i]/6);
tc[3]-=dlt*2; th[i]-=dlt*6;
}
if (tc[3]==1)
{
int pos=0; for (i=1;i<=m;++i) if (th[i]>th[pos]) pos=i;
--tc[3]; th[pos]-=3;
}
for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==4) --tc[3],th[i]-=3;
for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==2) --tc[3],th[i]=0;
for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==1) --tc[3],th[i]=0;
for (i=1;i<=m&&tc[2]>0;++i) if (th[i]>0)
{
int dlt=min(tc[2],th[i]/2);
tc[2]-=dlt; th[i]-=dlt*2;
}
for (i=1;i<=m&&tc[2]>0;++i) if (th[i]==1) --tc[2],th[i]=0;
for (i=1;i<=m&&tc[1]>0;++i)
{
int dlt=min(tc[1],th[i]);
tc[1]-=dlt; th[i]-=dlt;
}
for (i=1;i<=m;++i) if (th[i]>0) return 0;
return 1;
}
signed main()
{
//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (i=1;i<=3;++i) c[i]=0;
for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),++c[a[i]];
for (scanf("%lld",&m),i=1;i<=m;++i) scanf("%lld",&h[i]);
int l=1,r=1e14,mid,ret=0; while (l<=r)
if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
printf("%lld\n",ret);
}
return 0;
}
J. Ants
我对这题题意一知半解,但据说就是个模拟题,不过实现细节比较考验人需要仔细思考一下
用two pointers
或队列实现的话可能比较简单
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
const int LEN = 1e9+1;
int A[N], d[N];
struct Node{
int id, pos;
bool operator<(const Node &b){return pos<b.pos;}
};
vector<Node> vL, vR;
bool vis[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, L, R; cin >> n >> L >> R;
for (int i=1; i<=n; ++i) cin >> A[i];
for (int i=1; i<=n; ++i) cin >> d[i];
for (int i=1; i<=n; ++i){
if (0==d[i]){
vL.push_back(Node{i, A[i]}), vR.push_back(Node{i, LEN+A[i]});
vL.push_back(Node{i, 2*LEN+A[i]}), vR.push_back(Node{i, 2*LEN+LEN+A[i]});
}else{
vL.push_back(Node{i, 2*LEN-A[i]}), vR.push_back(Node{i, LEN-A[i]});
vL.push_back(Node{i, 2*LEN+2*LEN-A[i]}), vR.push_back(Node{i, 2*LEN+LEN-A[i]});
}
}
sort(vL.begin(), vL.end()); sort(vR.begin(), vR.end());
int mn=min(L, R);
int ans=0;
if (mn>=n) ans+=2*LEN*(mn/n), L-=mn/n*n, R-=mn/n*n;
int pL=0, pR=0;
int mx=0;
while (pL<vL.size() && pR<vR.size()){
if (vL[pL].pos<=vR[pR].pos){
if (!vis[vL[pL].id]){
if (L>0) --L;
else mx=max(mx, vL[pL].pos), vis[vL[pL].id]=true;
}
++pL;
}else{
if (!vis[vR[pR].id]){
if (R>0) --R;
else mx=max(mx, vR[pR].pos), vis[vR[pR].id]=true;
}
++pR;
}
}
while (pL<vL.size()){
if (!vis[vL[pL].id]){
if (L>0) --L;
else mx=max(mx, vL[pL].pos), vis[vL[pL].id]=true;
}
++pL;
}
while (pR<vR.size()){
if (!vis[vR[pR].id]){
if (R>0) --R;
else mx=max(mx, vR[pR].pos), vis[vR[pR].id]=true;
}
++pR;
}
cout << ans+mx << '\n';
return 0;
}
K. K-skip Permutation
签到题,把\(\bmod k\)相同的数升序排在一起即可
#include<bits/stdc++.h>
using namespace std;
signed main(){
int n, k; scanf("%d%d", &n, &k);
vector<int> vec;
for (int i=1; i<=k; ++i){
for (int j=0; j*k+i<=n; ++j) vec.push_back(j*k+i);
}
for (int i=0; i<n; ++i){
if (i>0) putchar(' ');
printf("%d", vec[i]);
}
return 0;
}
L. Spicy Restaurant
乍一看很吓人,其实仔细看数据范围会发现点权很小
因此可以做\(100\)遍BFS,每次加入点权等于当前值的所有点,做一个多源BFS来更新到每个点的答案即可
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const int INF = 0x3f3f3f3f;
int n, m, q;
struct Qry{
int p, ans;
}qry[N];
vector<int> vec[105], ask[105];
vector<int> edg[N];
int dis[N];
int que[N], fr=0, ed=-1;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> q;
for (int i=1; i<=n; ++i){
int w; cin>>w;
vec[w].push_back(i);
}
for (int i=1; i<=m; ++i){
int u, v; cin >> u >> v;
edg[u].push_back(v); edg[v].push_back(u);
}
for (int i=1; i<=q; ++i){
int p, a; cin >> p >> a;
qry[i].p=p;
ask[a].push_back(i);
}
memset(dis, 0x3f, (n+1)*sizeof(int));
for (int w=1; w<=100; ++w){
fr=0, ed=-1;
for (int x : vec[w]) que[++ed]=x, dis[x]=0;
while (fr<=ed){
int u=que[fr++];
for (int v : edg[u]){
if (dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
que[++ed]=v;
}
}
}
for (int id : ask[w]){
qry[id].ans = (dis[qry[id].p]<INF ? dis[qry[id].p] : -1);
}
}
for (int i=1; i<=q; ++i) printf("%d\n", qry[i].ans);
return 0;
}
M. True Story
题意初看不明所以,其实仔细一想会发现如果一个人已经选择出发了,那么他一定能坐上飞机
因此就是找一个最大的\(p_i-t_i\),每个人最多能用的时间就是这个,直接判断即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int p[N], t[N], s[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, x; cin >> n >> k >> x >> p[0];
for (int i=1; i<=n; ++i) cin >> s[i];
for (int i=1; i<=k; ++i) cin >> t[i];
for (int i=1; i<=k; ++i) cin >> p[i];
int ret=0;
for (int i=0; i<=k; ++i){
ret=max(ret, p[i]-t[i]);
}
int cnt=0;
for (int i=1; i<=n; ++i){
if (ret*s[i]>=x) ++cnt;
}
cout << cnt << '\n';
return 0;
}
Postscript
这场博客写的巨快,因为没啥难的题
不知道是省赛都是这个难度还是这场特别简单,久违地写了两位数的题
标签:Provincial,cur,Contest,int,Programming,++,--,th,include From: https://www.cnblogs.com/cjjsb/p/17871758.html