A - Love "A"
time limit per test1 second . memory limit per test256 megabytes
Alice has a string ?s. She really likes the letter "a". She calls a string good if strictly more than half of the characters in that string are "a"s. For example "aaabb", "axaa" are good strings, and "baca", "awwwa", "" (empty string) are not.
Alice can erase some characters from her string ?s. She would like to know what is the longest string remaining after erasing some characters (possibly zero) to get a good string. It is guaranteed that the string has at least one "a" in it, so the answer always exists.Input
The first line contains a string ?s (1≤|?|≤501≤|s|≤50) consisting of lowercase English letters. It is guaranteed that there is at least one "a" in ?s.Output
Print a single integer, the length of the longest good string that Alice can get after erasing some characters from ?s.
Examples
input
xaxxxxa
output
3
input
aaabaa
output
6
Note
In the first example, it's enough to erase any four of the "x"s. The answer is 33 since that is the maximum number of characters that can remain.
In the second example, we don't need to erase any characters.
签到
#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 maxn=(int)1e5+100;
int main(){
string s;cin>>s;int len=s.length(),tot=0;;
rep(i,0,len-1) if(s[i]=='a') tot++;
cout<<min(tot*2-1,len)<<endl;
}
B - Hate "A"
time limit per test1 second memory limit per test256 megabytes
Bob has a string ?s consisting of lowercase English letters. He defines ?′s′ to be the string after removing all "a" characters from ?s(keeping all other characters in the same order). He then generates a new string ?t by concatenating ?s and ?′s′. In other words, ?=?+?′t=s+s′(look at notes for an example).
You are given a string ?t. Your task is to find some ?s that Bob could have used to generate ?t. It can be shown that if an answer exists, it will be unique.Input
The first line of input contains a string ?t (1≤|?|≤1051≤|t|≤105) consisting of lowercase English letters.Output
Print a string ?s that could have generated ?t. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).
Examples
input
aaaaa
output
aaaaa
input
aacaababc
output
:(
input
ababacacbbcc
output
ababacac
input
baba
output
:(
Note
In the first example, we have ?=s= "aaaaa", and ?′=s′= "".
In the second example, no such ?s can work that will generate the given ?t.
In the third example, we have ?=s= "ababacac", and ?′=s′= "bbcc", and ?=?+?′=t=s+s′= "ababacacbbcc".
可知答案串必定是原串的某个前缀，那么可以暴力枚举答案
#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 maxn=(int)1e5+100;
int main(){
string s,c;cin>>s;int len=s.length(); c.clear();
rep(i,0,len-1){
if(s[i]!='a') c+=s[i];
if(c==s.substr(i+1)){
cout<<s.substr(0,i+1)<<endl;
exit(0);
}
}
cout<<":(\n";
}
C - Tree Diameter
time limit per test4 seconds memory limit per test256 megabytes
There is a weighted tree with ?n nodes and ?−1n−1 edges. The nodes are conveniently labeled from 11 to ?n. The weights are positive integers at most 100100. Define the distance between two nodes to be the sum of edges on the unique path between the nodes. You would like to find the diameter of the tree. Diameter is the maximum distance between a pair of nodes.
Unfortunately, the tree isn't given to you, but you can ask some questions about it. In one question, you can specify two nonempty disjoint sets of nodes ?p and ?q, and the judge will return the maximum distance between a node in ?p and a node in ?q. In the words, maximum distance between ?x and ?y, where ?∈?x∈p and ?∈?y∈q. After asking not more than 99 questions, you must report the maximum distance between any pair of nodes.Interaction
Each test contains multiple test cases. The first line contains the number of test cases ?t (1≤?≤10001≤t≤1000). Description of the test cases follows.
The first line of each test case contains an integer ?n (2≤?≤1002≤n≤100) — the number of nodes in the tree.
To ask a question, print "?1 ?2 ?1 ?2 … ??1 ?1 ?2 … ??2k1 k2 a1 a2 … ak1 b1 b2 … bk2" (?1,?2≥1(k1,k2≥1 and ?1+?2≤?k1+k2≤n). These two sets must be nonempty and disjoint. The judge will respond with a single integer max?,?????(??,??)maxp,qdist(ap,bq). If you ever get a result of −1−1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.
After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.
When you are ready to answer, print "−1 ?−1 d", where ?d is the maximum shortest distance over all pairs of nodes.
You can only ask at most 99 questions per test case.
Hack Format
To hack, use the following format. Note that you can only hack with one test case.
The first line should contain a single integer ?t (?=1t=1).
The second line should contain a single integer ?n (2≤?≤1002≤n≤100).
Each of the next ?−1n−1 lines should contain three integers ??,??,??ai,bi,ci (1≤??,??≤?1≤ai,bi≤n, 1≤??≤1001≤ci≤100). This denotes an undirected edge between nodes ??ai and ??bi with weight ??ci. These edges must form a tree.
Example
input
2
5
9
6
10
9
10
2
99
output
1 4 1 2 3 4 5
1 4 2 3 4 5 1
1 4 3 4 5 1 2
1 4 4 5 1 2 3
1 4 5 1 2 3 4
-1 10
1 1 1 2
-1 99
Note
In the first example, the first tree looks as follows:
In the first question, we have ?=1p=1, and ?=2,3,4,5q=2,3,4,5. The maximum distance between a node in ?p and a node in ?q is 99 (the distance between nodes 11 and 55).
The second tree is a tree with two nodes with an edge with weight 9999 between them.
有趣的交互题；
首先我们有结论：对于任意点，和它距离最远的点必定是直径的某个端点；于是我们可以先查询任意一个点到其余所有点的最大距离，然后再二分查找距离最大的那个点，找到以后再一次查询就可以找到答案；
最坏情况下需要查询1+log2(99)+1=9次；
#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 maxn=(int)1e5+100;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
cout<<"1 "<<n-1; rep(i,1,n) cout<<" "<<i; cout<<endl;
int k;cin>>k;
int l=2,r=n;
while(l<r){
int mid=l+r>>1;
cout<<"1 "<<mid-l+1<<" 1"; rep(i,l,mid) cout<<" "<<i; cout<<endl;
int x;cin>>x;
if(x<k) l=mid+1;else r=mid;
}
cout<<"1 "<<n-1<<" "<<l; rep(i,1,n) if(i!=l) cout<<" "<<i; cout<<endl;
int x;cin>>x;
cout<<"-1 "<<x<<endl;
}
}
D - Frog Jumping
time limit per test2 seconds memory limit per test256 megabytes
A frog is initially at position 00 on the number line. The frog has two positive integers ?a and ?b. From a position ?k, it can either jump to position ?+?k+a or ?−?k−b.
Let ?(?)f(x) be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval [0,?][0,x]. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from 00.
Given an integer ?m, find ∑??=0?(?)∑i=0mf(i). That is, find the sum of all ?(?)f(i) for ?i from 00 to ?m.Input
The first line contains three integers ?,?,?m,a,b (1≤?≤109,1≤?,?≤1051≤m≤109,1≤a,b≤105).Output
Print a single integer, the desired sum.
Examples
input
7 5 3
output
19
input
1000000000 1 2019
output
500000001500000001
input
100 100000 1
output
101
input
6 4 5
output
10
Note
In the first example, we must find ?(0)+?(1)+…+?(7)f(0)+f(1)+…+f(7). We have ?(0)=1,?(1)=1,?(2)=1,?(3)=1,?(4)=1,?(5)=3,?(6)=3,?(7)=8f(0)=1,f(1)=1,f(2)=1,f(3)=1,f(4)=1,f(5)=3,f(6)=3,f(7)=8. The sum of these values is 1919.
In the second example, we have ?(?)=?+1f(i)=i+1, so we want to find ∑109?=0?+1∑i=0109i+1.
In the third example, the frog can't make any jumps in any case.
首先如果没有限制条件，那么很容易想到坐标轴上所有gcd(a,b)的倍数都可以走到，这个值是等差数列。但是对于小于a+b的坐标是不严格满足这个式子的，考虑到a,b<2e5,可以直接暴力求答案，每次贪心的走，可以k-b就k-b，否则才k+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 int maxn=(int)2e5+100;
int vis[maxn],step[maxn],pos=0;
ll gcd(ll x, ll y){return y?gcd(y,x%y):x;}
int main(){
ll m,a,b;cin>>m>>a>>b;
const ll g=gcd(a,b);ll last=m/g+1;
ll ans=(1+last)*last/2*g-(last*g-1-m)*last;
vis[step[++pos]=0]=1;
while(1){
++pos;
step[pos]=step[pos-1]>=b?step[pos-1]-b:step[pos-1]+a;
if(vis[step[pos]]) break;
vis[step[pos]]=1;
} --pos;
for(int i=0,j=1;i<a+b&&i<=m;++i){
ans-=i/g+1;
while(step[j]<=i&&j<=pos) ++j;--j;
ans+=j;
}
cout<<ans<<endl;
}
