A. Alarm Clock
题意：
给出 (a,b,c,d~(1 leq a,b,c,d leq 10^9)) ，Polycarp 一开始先睡 (b) 分钟，然后从第 (b) 分钟开始 闹钟每隔 (c) 分钟响一次，Polycarp 醒来之后若总睡眠时间达到 (a) 分钟以上，则直接起床，否则继续睡，但他每次得花 (d) 分钟才能睡着；问能否睡够 (a) 分钟，若可以输出总花费时间，若不能输出 (-1)；
(t~(1 leq t leq 1000)) 组测试数据；
分析：
模拟，考虑几种情况：
- 若 (b>=a) ，则花费即 (b)；
- 若 (b<a) 且 (c<=d) ，则无解；
- 若 (b<a) 且 (c>d)，则从第 (b) 分钟之后每 (c) 分钟补充 (c-d) 分钟睡眠时间；
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t,a,b,c,d;
cin>>t;
while(t--)
{
cin>>a>>b>>c>>d;
if(a<=b) cout<<b<<endl;
else if(c<=d) cout<<-1<<endl;
else{
ll res=b; a-=b;
ll sub=c-d;
ll tim=a/sub; if(a%sub) tim++;
res+=tim*c;
cout<<res<<endl;
}
}
}
B. Ternary String
题意：
给出一个仅包含 (1,2,3) 的字符串 (s~(1 leq |s| leq 200000)) ，求最短的连续区间，使得这个区间内都出现过 (1,2,3)，输出这个最短的长度，无解输出 (0)；
(t~(1 leq t leq 20000)) 组测试数据；
分析：
可以二分或者单调栈，二分的话需要维护一下 (1,2,3) 出现的前缀和；
二分
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 2E5+10;
string s;
int a[N],b[N],c[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n;
cin>>t;
while(t--)
{
cin>>s; n=s.length();
rep(i,0,n) a[i]=b[i]=c[i]=0;
rep(i,1,n)
{
int x=s[i-1]-'0';
if(x==1) a[i]=1;
if(x==2) b[i]=1;
if(x==3) c[i]=1;
}
rep(i,2,n) a[i]+=a[i-1],b[i]+=b[i-1],c[i]+=c[i-1];
int L=3,R=n,ans=0;
while(L<=R)
{
int m=(L+R)>>1;
int ok=0;
rep(i,1,n)if(i+m-1>n) break;
else{ int k=i+m-1;
if(a[k]-a[i-1]&&b[k]-b[i-1]&&c[k]-c[i-1])
{
ok=1;break;
}
}
if(ok) ans=m,R=m-1;
else L=m+1;
}
cout<<ans<<endl;
}
}
单调栈
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n;
cin>>t;
while(t--)
{
cin>>s; n=s.length();
int ANS=n+1,num[4]={0},cnt=0;
rep(i,0,n-1)
{
int x=s[i]-'0';
num[x]++;
cnt++;
while(num[1]&&num[2]&&num[3])
{
int pre=i-cnt+1;
x=s[pre]-'0';
if(num[x]>1) num[x]--,cnt--;
else break;
}
if(num[1]&&num[2]&&num[3]) ANS=min(ANS,cnt);
if(ANS==3) break;
}
if(ANS>n) cout<<0<<endl;
else cout<<ANS<<endl;
}
}
C1. Simple Polygon Embedding
题意：
给出 (n~(n in even 且 2 leq n leq 200))，求能完全容纳下正 (2*n) 多边形的正方形的最短边长；(T~(1 leq T leq 200)) 组测试数据；
分析：
(n in even) ，所以 (2*n) 显然是 (4) 的倍数，再套来官方题解的图
所以不难理解，最短边长就是 (2 imes MN) ，即 (ans=frac{1}{tanfrac{pi}{2cdot n}})，推一遍
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const double PI = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
double ans=1.0/tan(PI/(2*n));
cout<<setprecision(10)<<ans<<endl;
}
}
C2. Not So Simple Polygon Embedding
题意：
和 (C1) 唯一的不同点就是 (n in odd~(3 leq n leq 199))；
分析：
(n in odd)，所以 (2*n) 不再是 (4) 的倍数，但因为仍是正偶数多边形( (2n>4))，所以肯定可以通过旋转 使得有 (4) 个点正好卡在正方形的四条边上，再套图
所以需要求第一张图到第二张图的旋转角度；再观察，图一和图三是等价的，所以旋转角度为 (frac{angle O}{2}) ，即 (ans=frac{cos(frac{pi}{4n})}{frac{pi}{2n}})；
(当时我没想到旋转角度正好是一半，直接二分角度的，也A了)
代码：(贴下二分的)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const double PI = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n;
cin>>t;
while(t--)
{
cin>>n; n*=2;
double a=2*PI/(2*n);
double L=0,R=a;
rep(i,0,100)
{
double m=(L+R)/2;
if(cos(m)>cos(a-m)) L=m;
else R=m;
}
double b=(PI-2*PI/n)/2;
double len=0.5/cos(b);
double ans=len*cos(L)*2;
cout<<setprecision(10)<<ans<<endl;
}
}
D. Multiset
题意：
先给出 (n) 和 (q~(1 leq n,q leq 10^6))，接着给出初始大小为 (n) 的多重集 (a~(1 leq a_1 leq a_2 leq cdots leq a_n leq n))，再给出 (q) 个操作，每个操作给出 (k_i)，分两种：
- if (1 leq k_i leq n) ，那么把 (k_i) 加入多重集；
- if (k_i<0) ，那么就删除多重集中从小到大排第 (|k_i|) 的数；
最后求经过 (q) 次操作之后，多重集是否为空，是则输出 (0) ，否则输出多重集内任意一个元素就可以了；
分析：
多重集为空的情况不难想，即 (操作2=操作1+n) ；若不为空，仅要求输出任意一个集合内元素即可，看一看时限，考虑 (O(nlogn)) 的做法；首先对于一个数 (m) ，我们考虑有没有小于等于它的数最后还在多重集内，因为对 (m) 产生影响的只能是小于等于它的数 (只有在多重集内添加或者删除小于等于 (m) 的数才会对它的排序造成影响) ，所以判断即更新维护小于等于 (m) 的数的数量(O(n+m)) ，二分这个 (m) ，复杂度就达到要求了；(线段树和树状数组也可以)
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 1E6+10;
vector<int>a,b;
int n,q;
int ask(int m)
{
int cnt=0;
for(auto v:a)if(v<=m)cnt++; //初始多重集内<=m的数量
for(auto v:b)
if(v>0&&v<=m) cnt++; //操作1添加v
else if(v<0&&abs(v)<=cnt) cnt--; //操作2删除第|v|个数
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
a.resize(n);
b.resize(q);
rep(i,0,n-1)cin>>a[i];
rep(i,0,q-1)cin>>b[i];
if(ask(1e7)==0) cout<<0,exit(0);
//相当于判断多重集是否为空
int L=0,R=1e6+1,ans;
while(R-L>1)
{
int m=(L+R)>>1;
if(ask(m)>0) R=m; //aks(m)>0,证明最后多重集中存在<=m的数，所以更新上界；
else L=m;
}
cout<<R;
}
树状数组
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 2E6+60;
int a[N],n,q;
int lowbit(int x){return x&(-x);}
void add(int x,int k){
for(int i=x;i<N;i+=lowbit(i)) a[i]+=k;
}
ll query(int x){
ll res=0;
for(int i=x;i;i-=lowbit(i)) res+=a[i];
return res;
}
void del(int x){
int res=0;
for(int i=19;i>0;i--)
if(a[res|(1<<i)]<x) x-=a[res|=(1<<i)];
if(a[res|1]<x) add(res+2,-1);
else add(res+1,-1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
rep(i,1,n){
int x;cin>>x;
add(x,1);
}
rep(i,1,q){
int x;cin>>x;
if(x>0) add(x,1);
else del(-x);
}
if(!query(n)) cout<<0,exit(0);
rep(i,1,n) if(query(i)) cout<<i,exit(0);
}
E. Graph Coloring
题意：
给顶点数为 (n) 的无向图(可能不连通，有自环，重复边)，现在要求你把这张图染三色(颜色种类从1到3)，要求：
- (n1,n2,n3) 分别对应最后染色完三种颜色的数量；
- 对于每条边 ((u,v)) 要求 (|col_u-col_v|=1) ，(col_x) 即顶点 (x) 的颜色种类；
问是否存在合理的染色方式，不存在则输出 (NO)，否则输出 (YES) 和 具体方案；
分析：
有了条件 2 的限制，其实这里的染三色就相当于染双色(1,3一类)，所以判断这个图是否满足条件2 即 判断这个图是否为 二分图 ，判断就搜索一遍试着染色(双色)就可以了；然后想条件1，因为我们已经给图染双色了，而图可能是由若干个联通块组成的，所以这就是明显的分组背包了；
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 5000+10;
int lab[N],be[N],cnt,A[N],B[N],ANS[N];
int n,n1,n2,n3,m;
bool dp[N][N];
vector<int>G[N];
bool dfs(int u,int nO)
{
lab[u]=nO; //第u个顶点的颜色
be[u]=cnt; //第u个顶点属于第几个联通块
if(nO==1) A[cnt]++; //第cnt个联通块颜色A的数量
else B[cnt]++; //第cnt个联通块颜色B的数量
for(auto v:G[u])
{
if(lab[v]==0){
if(!dfs(v,3-nO))return 0;
}
else{
if(lab[u]==lab[v]) return 0;
}
}
return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>n1>>n2>>n3;
rep(i,1,m){
int u,v;cin>>u>>v;
G[u].pb(v),G[v].pb(u);
}
rep(i,1,n) if(!lab[i]){
++cnt; //第cnt个联通块
if(!dfs(i,1)) cout<<"NO",exit(0); //染色失败，无解
}
memset(dp,false,sizeof dp);
dp[0][0]=1;
rep(i,1,cnt) //分组背包
{
rep(k,A[i],n2) dp[i][k]|=dp[i-1][k-A[i]];
rep(k,B[i],n2) dp[i][k]|=dp[i-1][k-B[i]];
}
if(!dp[cnt][n2]) cout<<"NO",exit(0);
cout<<"YES
";
int k=n2;
//这里可以不用另外记录路径，只需要利用DP数组的性质就可以找到一条合理的路径(因为每个联通块至多只有两个选择)
for(int i=cnt;i>=1;i--)
{
if(dp[i-1][k-A[i]]) ANS[i]=1,k-=A[i];
else ANS[i]=2,k-=B[i];
}
rep(i,1,n)
{
int num=ANS[be[i]];
if(lab[i]==num) cout<<2;
else if(n1) cout<<1,n1--; //1,3是一类的，所以用完了1剩下的用3就可以了
else cout<<3;
}
}
F. Summoning Minions
题意：
(n) 张牌，最多选 (k) 张，可以选了之后再删 ((1 leq k leq n leq 75)) ；每张牌初始战力值为 (a_i)，选第 (i) 张牌可以给之前选的牌(删去的不算)的战力值都加上 (b_i) ，求一种具体的选删方式，使得最后的 (k) 张牌的战力值总和最大；
分析：
稍微想一下，肯定是先选择 (k-1) 张牌，然后不断选删第 (k) 张直到最后，那么为了最大化战力值总和，所以 (b) 大的肯定先放后面；所以先按照 (b) 值排升序，然后 dp[i][j] 表示排序后前 (i) 张牌，选中 (j) 张的最大战力值(这里的选中意思是这 (j) 张牌在最后的 (k) 张牌中)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 75+5;
int dp[N][N];
bool path[N][N],mark[N];
struct node{
int a,b,id;
bool operator < (const node& x)const{return b<x.b;}
}e[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n,k;cin>>t;
while(t--)
{
cin>>n>>k;
rep(i,1,n)cin>>e[i].a>>e[i].b,e[i].id=i;
sort(e+1,e+n+1);
memset(dp,-1,sizeof(dp));
memset(path,0,sizeof(path));
memset(mark,0,sizeof(mark));
dp[0][0]=0;
rep(i,1,n)rep(j,0,min(i,k))
{
if(dp[i-1][j]>=0)
dp[i][j]=dp[i-1][j]+e[i].b*(k-1); //这张牌不属于最后k张牌之一
if(j>0&&dp[i-1][j-1]>=0&&dp[i][j]<dp[i-1][j-1]+e[i].a+e[i].b*(j-1))
{
dp[i][j]=dp[i-1][j-1]+e[i].a+e[i].b*(j-1);
path[i][j]=1;
}
}
int j=k;
frep(i,n,1)if(path[i][j]) mark[e[i].id]=1,j--;
cout<<k+(n-k)*2<<endl;
int end,cnt=0;;
rep(i,1,n)if(mark[e[i].id]){
if(++cnt==k) {end=e[i].id;break;}
cout<<e[i].id<<' ';
}
rep(i,1,n)if(!mark[e[i].id])cout<<e[i].id<<' '<<-e[i].id<<' ';
cout<<end<<endl;
}
}
G. Find a Gift
题意： (交互题)
(n) 个盒子，(k) 个装有礼物，剩下的装有石头 ((2 leq n leq 1000,1 leq k leq frac{n}{2})) ，石头的重量完全相同，礼物的重量可能不相同但均小于石头；现在你有至多 (50) 次机会询问任意两堆盒子的重量比较的结果，求第一个装有礼物的盒子的最小编号；
分析：
前 (30) 次随机询问比较第 (1) 个盒子和其它盒子的重量，若询问完还是 (1) 号盒子最重，则它装有石头的概率就是
几乎为 (1) ，所以这时可以确定 (1) 号盒子装有石头，然后按 (2) 的幂次比较：([1,1] 和 [2,2] , [1,2] 和 [2,4] cdots)，直到重量不等，则后面一堆必有装有礼物的盒子，再二分就可以了；
代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n,k;
int ask(int l1,int r1,int l2,int r2)
{
cout<<"? "<<r1-l1+1<<" "<<r2-l2+1<<endl;
rep(i,l1,r1-1) cout<<i<<' ';cout<<r1<<endl;
rep(i,l2,r2-1) cout<<i<<' ';cout<<r2<<endl;
cout.flush();
string s;cin>>s;
if(s[0]=='F') return -1;
if(s[0]=='E') return 0;
if(s[0]=='S') return 1;
}
void solve()
{
srand(0);
rep(i,1,30)
{
int cnt=2+rand()%(n-1);
int ans=ask(1,1,cnt,cnt);
if(ans==1)
{
cout<<"! 1
";
cout.flush();
return;
}
}
int len=1;
while(1)
{
if(len*2<=n){
int ans=ask(1,len,len+1,len*2);
if(ans!=0) break;
}
else{
int ans=ask(1,n-len,len+1,n);
if(ans!=0) break;
}
len<<=1;
}
int L=len+1,R=min(2*len,n);
while(L<=R)
{
int m=(L+R)>>1;
int ans=ask(1,m-L+1,L,m);
if(ans==0) L=m+1;
else R=m-1;
}
cout<<"! "<<L<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;cin>>t;
while(t--)
{
cin>>n>>k;
solve();
}
}