A. Alarm Clock
time limit per test2 seconds memory limit per test256 megabytes
Polycarp has spent the entire day preparing problems for you. Now he has to sleep for at least a minutes to feel refreshed.
Polycarp can only wake up by hearing the sound of his alarm. So he has just fallen asleep and his first alarm goes off in b minutes.
Every time Polycarp wakes up, he decides if he wants to sleep for some more time or not. If he's slept for less than a minutes in total, then he sets his alarm to go off in c minutes after it is reset and spends d minutes to fall asleep again. Otherwise, he gets out of his bed and proceeds with the day.
If the alarm goes off while Polycarp is falling asleep, then he resets his alarm to go off in another c minutes and tries to fall asleep for d minutes again.
You just want to find out when will Polycarp get out of his bed or report that it will never happen.
Please check out the notes for some explanations of the example.Input
The first line contains one integer \(t (1 \le t \le 1000)\) — the number of testcases.
The only line of each testcase contains four integers \(a, b, c, d (1 \le a, b, c, d \le 10^9)\) — the time Polycarp has to sleep for to feel refreshed, the time before the first alarm goes off, the time before every succeeding alarm goes off and the time Polycarp spends to fall asleep.Output
For each test case print one integer. If Polycarp never gets out of his bed then print -1. Otherwise, print the time it takes for Polycarp to get out of his bed.ExampleinputCopy
7 10 3 6 4 11 3 6 4 5 9 4 10 6 5 2 3 1 1 1 1 3947465 47342 338129 123123 234123843 13 361451236 361451000
outputCopy
27 27 9 -1 1 6471793 358578060125049
Note
In the first testcase Polycarp wakes up after 3 minutes. He only rested for 3 minutes out of 10 minutes he needed. So after that he sets his alarm to go off in 6 minutes and spends 4 minutes falling asleep. Thus, he rests for 2 more minutes, totaling in 3+2=5 minutes of sleep. Then he repeats the procedure three more times and ends up with 11 minutes of sleep. Finally, he gets out of his bed. He spent 3 minutes before the first alarm and then reset his alarm four times. The answer is \(3+4 \cdot 6 = 27\).
The second example is almost like the first one but Polycarp needs 11 minutes of sleep instead of 10. However, that changes nothing because he gets 11 minutes with these alarm parameters anyway.
In the third testcase Polycarp wakes up rested enough after the first alarm. Thus, the answer is b=9.
In the fourth testcase Polycarp wakes up after 5 minutes. Unfortunately, he keeps resetting his alarm infinitely being unable to rest for even a single minute 🙁
英语阅读理解题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
ll a,b,c,d;cin>>a>>b>>c>>d;
if(b>=a){cout<<b<<endl;return;}
if(d>=c){cout<<"-1\n";return;}
cout<<b+(a-b+c-d-1)/(c-d)*c<<endl;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int T;cin>>T;
while(T--) solve();
}
B. Ternary String
time limit per test2 seconds memory limit per test256 megabytes
You are given a string s such that each its character is either 1, 2, or 3. You have to choose the shortest contiguous substring of s such that it contains each of these three characters at least once.
A contiguous substring of string s is a string that can be obtained from s by removing some (possibly zero) characters from the beginning of s and some (possibly zero) characters from the end of s.Input
The first line contains one integer \(t (1 \le t \le 20000) \\)— the number of test cases.
Each test case consists of one line containing the string \(s (1 \le |s| \le 200000)\). It is guaranteed that each character of s is either 1, 2, or 3.
The sum of lengths of all strings in all test cases does not exceed 200000.Output
For each test case, print one integer — the length of the shortest contiguous substring of s containing all three types of characters at least once. If there is no such substring, print 0 instead.ExampleinputCopy
7 123 12222133333332 112233 332211 12121212 333333 31121
outputCopy
3 3 4 4 0 0 4
Note
Consider the example test:
In the first test case, the substring 123 can be used.
In the second test case, the substring 213 can be used.
In the third test case, the substring 1223 can be used.
In the fourth test case, the substring 3221 can be used.
In the fifth test case, there is no character 3 in s.
In the sixth test case, there is no character 1 in s.
In the seventh test case, the substring 3112 can be used.
这题不会建议不要打ACM了哦
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
char s[maxn];
void solve(){
scanf("%s",s+1);
int n=strlen(s+1),pre[3]={-1,-1,-1},ans=mod;
rep(i,1,n){
pre[s[i]-'1']=i;
int x=*min_element(pre,pre+3);
if(~x) ans=min(ans,i-x+1);
} if(ans==mod) ans=0;
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C2. Not So Simple Polygon Embedding
time limit per test2 seconds memory limit per test256 megabytes
The statement of this problem is the same as the statement of problem C1. The only difference is that, in problem C1, n is always even, and in C2, n is always odd.
You are given a regular polygon with \(2 \cdot n\) vertices (it's convex and has equal sides and equal angles) and all its sides have length 1. Let's name it as 2n-gon.
Your task is to find the square of the minimum size such that you can embed 2n-gon in the square. Embedding 2n-gon in the square means that you need to place 2n-gon in the square in such way that each point which lies inside or on a border of 2n-gon should also lie inside or on a border of the square.
You can rotate 2n-gon and/or the square.Input
The first line contains a single integer \(T (1 \le T \le 200)\) — the number of test cases.
Next T lines contain descriptions of test cases — one per line. Each line contains single odd integer \(n (3 \le n \le 199)\). Don't forget you need to embed 2n-gon, not an n-gon.Output
Print T real numbers — one per test case. For each test case, print the minimum length of a side of the square 2n-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-6}.ExampleinputCopy
3 3 5 199
outputCopy
1.931851653 3.196226611 126.687663595
稍微推亿下就出来了；
x是多边形的内角的一半，观察易得，多边形旋转x/2后是最优解；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const double pi=acos(-1.0);
void solve(){
int n;scanf("%d",&n);n*=2;
double x=pi/n,ans=0;
printf("%.10lf\n",cos(x/2)/sin(x));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Multiset
time limit per test1.5 seconds memory limit per test28 megabytes
Note that the memory limit is unusual.
You are given a multiset consisting of n integers. You have to process queries of two types:
- add integer k into the multiset;
- find the k-th order statistics in the multiset and remove it.
k-th order statistics in the multiset is the k-th element in the sorted list of all elements of the multiset. For example, if the multiset contains elements 1, 4, 2, 1, 4, 5, 7, and k = 3, then you have to find the 3-rd element in [1, 1, 2, 4, 4, 5, 7], which is 2. If you try to delete an element which occurs multiple times in the multiset, only one occurence is removed.
After processing all queries, print any number belonging to the multiset, or say that it is empty.Input
The first line contains two integers n and \(q (1 \le n, q \le 10^6)\) — the number of elements in the initial multiset and the number of queries, respectively.
The second line contains n integers\( a_1, a_2, ..., a_n (1 \le a_1 \le a_2 \le \dots \le a_n \le n)\) — the elements of the multiset.
The third line contains q integers \(k_1, k_2, ..., k_q\), each representing a query:
- if \(1 \le k_i \le n\), then the i-th query is "insert k_i into the multiset";
- if\( k_i < 0\), then the i-th query is "remove the |k_i|-th order statistics from the multiset". For this query, it is guaranteed that |k_i| is not greater than the size of the multiset.
Output
If the multiset is empty after all queries, print 0.
Otherwise, print any integer that belongs to the resulting multiset.ExamplesinputCopy
5 5 1 2 3 4 5 -1 -1 -1 -1 -1
outputCopy
0
inputCopy
5 4 1 2 3 4 5 -5 -1 -3 -1
outputCopy
3
inputCopy
6 2 1 1 1 2 3 4 5 6
outputCopy
6
Note
In the first example, all elements of the multiset are deleted.
In the second example, the elements 5, 1, 4, 2 are deleted (they are listed in chronological order of their removal).
In the third example, 6 is not the only answer.
树状数组练习题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int a[maxn],c[maxn],n,q,x;
int lowbit(int x){return x&(-x);}
void modify(int x,int add){
while(x<maxn){
c[x]+=add;
x+=lowbit(x);
}
}
int find_kth(int k){
int ans=0,cnt=0;
dep(i,20,0){
ans+=(1<<i);
if(ans>=maxn||cnt+c[ans]>=k) ans-=(1<<i);
else cnt+=c[ans];
}
return ans+1;
}
int main(){
scanf("%d%d",&n,&q);
rep(i,1,n) scanf("%d",&x),modify(x,1),a[x]++;
rep(i,1,q){
scanf("%d",&x);
if(x>0) modify(x,1),a[x]++;
else{
int pos=find_kth(-x);
modify(pos,-1);a[pos]--;
}
}int ans=0;
rep(i,1,n) if(a[i]) ans=i;
printf("%d\n",ans);
}
E. Graph Coloring
time limit per test2 seconds memory limit per test256 megabytes
You are given an undirected graph without self-loops or multiple edges which consists of n vertices and m edges. Also you are given three integers \(n_1, n_2 and n_3\).
Can you label each vertex with one of three numbers 1, 2 or 3 in such way, that:
- Each vertex should be labeled by exactly one number 1, 2 or 3;
- The total number of vertices with label 1 should be equal to n_1;
- The total number of vertices with label 2 should be equal to n_2;
- The total number of vertices with label 3 should be equal to n_3;
- |col_u - col_v| = 1 for each edge (u, v), where col_x is the label of vertex x.
If there are multiple valid labelings, print any of them.Input
The first line contains two integers n and \(m (1 \le n \le 5000; 0 \le m \le 10^5)\) — the number of vertices and edges in the graph.
The second line contains three integers \(n_1, n_2 and n_3 (0 \le n_1, n_2, n_3 \le n)\) — the number of labels 1, 2 and 3, respectively. It's guaranteed that \(n_1 + n_2 + n_3 = n\).
Next m lines contan description of edges: the i-th line contains two integers \(u_i, v_i (1 \le u_i, v_i \le n; u_i \neq v_i)\) — the vertices the i-th edge connects. It's guaranteed that the graph doesn't contain self-loops or multiple edges.Output
If valid labeling exists then print "YES" (without quotes) in the first line. In the second line print string of length n consisting of 1, 2 and 3. The i-th letter should be equal to the label of the i-th vertex.
If there is no valid labeling, print "NO" (without quotes).ExamplesinputCopy
6 3 2 2 2 3 1 5 4 2 5
outputCopy
YES 112323
inputCopy
5 9 0 2 3 1 2 1 3 1 5 2 3 2 4 2 5 3 4 3 5 4 5
outputCopy
NO
不保证连通性，所以可以对于每一个连通块单独考虑；首先有一个很显然的结论就是不能有奇环；其次，对于每个点涂的颜色来说只有两个状态，就是2和非2（合法的涂法必定是 2->非2->2->非2... 这样下去），那么也就是说对于一个连通块有两种涂法，问题就变为了：确定每个连通块的涂法使得最后的2的数量和题给一致（显然非2的可以不用考虑）；
我们令dp[i][j]表示前i个连通块，涂了j个2的方案是否可行，那么转移只需要\(dp[i][j]=max(dp[i-1][j-a[i]],dp[i-1][j-b[i]])\)即可，倒着回溯输出方案；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m,a[4];
struct Edge{
int v,w,nxt;
}g[maxn<<1];
int head[maxn],edge_tot;
void addedge(int u,int v,int w=1){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
int vis[5050],col[5050],dp[5050][5050];
int flag,c[2];
void dfs(int x,int fa,int st,int op){
if(vis[x]){
if((vis[fa]-vis[x])%2==0) flag=0;
return;
} vis[x]=st;c[st%2]++;
if(op==1){
if(st%2) col[x]=2;
else{
if(a[1]) a[1]--,col[x]=1;
else if(a[3]) a[3]--,col[x]=3;
}
}
for(int i=head[x],v;i;i=g[i].nxt) if((v=g[i].v)!=fa) dfs(v,x,st+1,op);
}
struct Q{int id,a,b;};
int main(){
scanf("%d%d%d%d%d",&n,&m,&a[1],&a[2],&a[3]);edge_tot=1;
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
vector<Q> v;
rep(i,1,n) if(!vis[i]){
flag=1;c[0]=c[1]=0;dfs(i,0,1,0);
if(!flag) return puts("NO"),0;
v.pb({i,c[1],c[0]});
}
dp[0][0]=1;
int sz=(int)v.size();
rep(i,0,sz-1) rep(j,0,n){
if(j-v[i].a>=0) dp[i+1][j]=max(dp[i+1][j],dp[i][j-v[i].a]);
if(j-v[i].b>=0) dp[i+1][j]=max(dp[i+1][j],dp[i][j-v[i].b]);
}
if(dp[sz][a[2]]==0) return puts("NO"),0;
puts("YES");
int now=a[2];
memset(vis,0,sizeof(vis));
dep(i,sz-1,0){
if(dp[i][now-v[i].a]) dfs(v[i].id,0,1,1),now-=v[i].a;
else if(dp[i][now-v[i].b]) dfs(v[i].id,0,2,1),now-=v[i].b;
}
rep(i,1,n) printf("%d",col[i]);
}
