这场gym感觉还挺好的，起手开了道A题自闭十分钟，发现是ACM赛制赶紧换题；
体验还挺好，简单题挺多，难题也不是不能做；
A. Sherlock Bones
time limit per test1.5 s memory limit per test256 MB
The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.
He is given a string of zeros and ones and length N.
Let F(x, y) equal to the number of ones in the string between indices x and y inclusively.
Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, sj is equal to 1, and F(i, j) is equal to F(j, k).Input
The first line of input is T – the number of test cases.
The first line of each test case is an integer N (3 ≤ N ≤ 2 × 105).
The second line is a string of zeros and ones of length N.Output
For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k).
Exampleinput
3 5 01010 6 101001 7 1101011
output
2
3
7
首先我们可以得到两个性质
- [i,k]中1的个数为奇数个
- (i,k)中1的个数大于0
首先记录一下前缀和a[i]表示1-i位中1的个数
从2-n枚举每个k，对于k找到他前面最近的1作为j，假设现在[j,k]区间内1的数量为x，那么现在的任务就是计算[1,j-1]这段区间内出现1的次数的奇偶性与x不同的子区间个数，显然是一个简单的区间dp问题；
用dp[i][0]表示[1,i]区间内出现偶数次1的子区间个数
用dp[i][1]表示[1,i]区间内出现奇数次1的子区间个数
那么对于str[i]='1'，偶区间等于奇区间，奇区间等于偶区间加[i,i]本身，str[i]='0'就是反过来
由于每次枚举的k不同，所以三元组也不同
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,a[maxn],dp[maxn][2];
char str[maxn];
void solve(){
memset(dp,0,sizeof(dp));
scanf("%d",&n);
scanf("%s",str+1);
a[0]=0; rep(i,1,n) a[i]=a[i-1]+str[i]-'0';
rep(i,1,n){
if(str[i]=='1'){
dp[i][0]=dp[i-1][1];
dp[i][1]=dp[i-1][0]+1;
}
else{
dp[i][1]=dp[i-1][1];
dp[i][0]=dp[i-1][0]+1;
}
}
ll ans=0,j=1;
rep(i,2,n){
if((a[i]-a[j-1])%2==0) ans+=dp[j-1][1];
else ans+=dp[j-1][0];
if(str[i]=='1') j=i;
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Unusual Team
time limit per test1.0 s memory limit per test256 MB
A lion, a mouse, and a beaver are one of the best teams at Animal University, and they have qualified to the ACM Arabella 2017 contest!
They want to choose their team name, and after many suggestions, they have reduced their options to two names: "FunkyMonkeys" and "WeWillEatYou".
They then created a poll on Facebook to help them with their final decision.
The results of the poll are now with Dr. Samer, and he will use the name with the highest votes to register the team. Can you help Dr. Samer to know which team name they will register with?Input
The first line of input is T – the number of test cases.
The first line of each test case contains two integers a, b (1 ≤ a, b ≤ 100) - the number of votes for "FunkyMonkeys" and "WeWillEatYou" respectively.Output
For each test case, output a single line containing "FunkyMonkeys" (without quotes), if that name received more points or tied with “WeWillEatYou”, otherwise output “WeWillEatYou”.
Exampleinput
2 15 20 70 70
output
WeWillEatYou
FunkyMonkeys
又是被英文gank的一题，签到
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,a,b;
int main(){
int T;cin>>T;
while(T--){
cin>>a>>b;
puts(b>a?"WeWillEatYou":"FunkyMonkeys");
}
}
C. Cheap Kangaroo
time limit per test1.0 s memory limit per test256 MB
There are N kangaroos going out to eat at an Indian restaurant. The ith kangaroo wants to eat exactly xi food. The kangaroos all want to order the same size of plates, but each one can order more than one plate for themselves if they need to. If the kangaroo orders more than he needs, he can simply hide the leftovers in his pouch.
At this Indian restaurant, the cost of the plate is the same as its size. Since Karl the Kangaroo is paying and is low on money, he wants to know what is the minimum cost to feed all N kangaroos and what is the largest possible size of the plates that satisfies this minimum cost?Input
The first line of input is T – the number of test cases.
The first line of each test case is an integer N (1 ≤ N ≤ 105).
The second line contains N space-separated integers xi (1 ≤ xi ≤ 109).Output
For each test case, output a line containing two space-separated integers – the minimum cost and the maximum plate size that corresponds to when the total cost is minimized.
Exampleinput
2 1 5 2 4 2
output
5 5
6 2
也是道签到题，显然如果size取1那答案就是所有xi累加，要求size最大那就求一下所有数的gcd就好了
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int n,a[maxn];
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
void solve(){
ll ans=0;
int ans2=0;
scanf("%d",&n);
rep(i,1,n){
scanf("%d",&a[i]);ans+=a[i];
if(i==1) ans2=a[1];
if(i==2) ans2=gcd(a[1],a[2]);
if(i>2) ans2=gcd(ans2,a[i]);
}
printf("%lld %d\n",ans,ans2);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Magical Bamboos
time limit per test1.0 s memory limit per test256 MB
In a magical forest, there exists N bamboos that don't quite get cut down the way you would expect.
Originally, the height of the ith bamboo is equal to hi. In one move, you can push down a bamboo and decrease its height by one, but this move magically causes all the other bamboos to increase in height by one.
If you can do as many moves as you like, is it possible to make all the bamboos have the same height?Input
The first line of input is T – the number of test cases.
The first line of each test case contains an integer N (1 ≤ N ≤ 105) - the number of bamboos.
The second line contains N space-separated integers hi (1 ≤ hi ≤ 105) - the original heights of the bamboos.Output
For each test case, output on a single line "yes” (without quotes), if you can make all the bamboos have the same height, and "no" otherwise.
Exampleinput
2 3 2 4 2 2 1 2
output
yes
no
每次选操作相当于把一颗竹子高度减少2，那么只要任意两颗竹子的高度差都是偶数就可以了
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int n,a[maxn];
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,2,n) if((a[i]-a[i-1])%2){puts("no");return;}
puts("yes");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
E. Competitive Seagulls
time limit per test1.0 s memory limit per test256 MB
There are two seagulls playing a very peculiar game. First they line up N unit squares in a line, all originally colored white.
Let L be the length of the longest continuous sub-segment of white unit squares. Let P be any prime that satisfies the condition that . The player can choose any P if it satisfies the conditions but if there is no value of P that does, then P is set to 1.
The current player then proceeds to choose any continuous sub-segment of white unit squares of length P and paint them black. The player who can’t make a move loses.
If both players play optimally and the first player starts, which player is going to win the game?Input
The first line of input is T – the number of test cases.
Each test case contains a line with a single integer N (1 ≤ N ≤ 107).Output
For each test case, output on a single line "first" (without quotes) if the first player would win the game, or "second" if the second would win.
Exampleinput
2 2 5
output
second
first
当n>4时，第一步先手可以选p为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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e7+100;
int n;
void solve(){
scanf("%d",&n);
if(n==2||n==3) puts("second");
else puts("first");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
G. Snake Rana
time limit per test4.0 s memory limit per test256 MB
Old Macdonald wants to build a new hen house for his hens. He buys a new rectangular area of size N by M. The night before he builds the hen house, snake Rana devises an evil plan to plant bombs in K distinct cells in the area to kill the hens and eat them for dinner later.
The morning of, Old Macdonald notices that each of the K cells, where snake Rana planted a bomb, have a marking on them. That won’t stop him though, all he must do is build the hen house in an area with no bombs.
Assume that rows are numbered from top to bottom, and columns are numbered from left to right. Old Macdonald now wants to know the number of ways he can choose sub-rectangles of top left coordinates (x1, y1) and bottom right coordinates (x2, y2) (x1 ≤ x2)(y1 ≤ y2) such that there are no bombs in the sub rectangle.Input
The first line of input is T – the number of test cases.
The first line of each test case is three integers N, M, and K (1 ≤ N, M ≤ 104) (1 ≤ K ≤ 20).
The next K lines each contains distinct pair of integers x, y (1 ≤ x ≤ N) (1 ≤ y ≤ M) - where (x, y) is the coordinate of the bomb.Output
For each test case, output a line containing a single integer - the number of sub-rectangles that don’t contain any bombs.
Exampleinput
3 2 2 1 2 2 6 6 2 5 2 2 5 10000 10000 1 1 1
output
5
257
2500499925000000
经典状压容斥，首先对于一个子矩阵，包含它的所有矩阵个数是mina*minb*(n-maxa+1)*(m-maxb+1)，其中(mina,minb)为左下角坐标，(maxa,maxb)为右上角坐标。
接下来用容斥做就好了，裸的模版题
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e7+100;
ll n,m;
int k;
struct node{
int x,y;
}p[22];
void solve(){
scanf("%lld%lld%d",&n,&m,&k);
ll ans=((1+n)*n/2)*((1+m)*m/2);
rep(i,0,k-1) scanf("%d%d",&p[i].x,&p[i].y);
for(int mk=1;mk<(1<<k);mk++){
int mina=maxn,minb=maxn,maxa=0,maxb=0,cnt=0;
rep(i,0,k-1) if(mk&(1<<i)){
++cnt;
mina=min(mina,p[i].x);maxa=max(maxa,p[i].x);
minb=min(minb,p[i].y);maxb=max(maxb,p[i].y);
}
ll res=1ll*mina*minb*(n-maxa+1)*(m-maxb+1);
if(cnt&1) ans-=res;
else ans+=res;
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
H. Mirrored String I
time limit per test1.0 s memory limit per test256 MB
The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings.
A mirrored string is a palindrome string that will not change if you view it on a mirror.
Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome.
e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not.
A palindrome is a string that is read the same forwards and backwards.
Can you tell if string S is a mirrored string?Input
The first line of input is T – the number of test cases.
Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters.Output
For each test case, output "yes" (without quotes) if the string S is a mirrored string, otherwise output "no".
Exampleinput
3 IOI ARABELLA RACECAR
output
yes
no
no
签到，模拟
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n;
char str[1010];
map<char,int> ck;
void work(){
scanf("%s",str+1);
int len=strlen(str+1);
rep(i,1,len) if(!ck[str[i]]){puts("no");return;}
rep(i,1,len/2) if(str[i]!=str[len-i+1]) {puts("no");return;}
puts("yes");
}
int main(){
ck['A']=1;ck['H']=1;ck['I']=1;ck['M']=1;ck['O']=1;ck['T']=1;ck['U']=1;
ck['V']=1;ck['W']=1;ck['X']=1;ck['Y']=1;
int T;cin>>T;
while(T--) work();
}
I. Mirrored String II
time limit per test1.0 s memory limit per test256 MB
Note: this is a harder version of Mirrored string I.
The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings.
A mirrored string is a palindrome string that will not change if you view it on a mirror.
Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome.
e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not.
A palindrome is a string that is read the same forwards and backwards.
Given a string S of length N, help the gorillas by printing the length of the longest mirrored substring that can be made from string S.
A substring is a (possibly empty) string of characters that is contained in another string S. e.g. "Hell" is a substring of "Hello".Input
The first line of input is T – the number of test cases.
Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters.Output
For each test case, output on a line a single integer - the length of the longest mirrored substring that can be made from string S.
Exampleinput
3 IOIKIOOI ROQ WOWMAN
output
4
1
3
长度只有1000，n^2暴力
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
const double pi=acos(-1.0);
char str[1010];
int len;
map<char,int> ck;
int check(int pos){
int p1=pos,p2=pos,p3=pos,p4=pos+1,flag1=1,flag2=1;
while(1){
if(flag1){
if(str[p1]==str[p2]&&ck[str[p1]]) p1--,p2++;
else flag1=0;
}
if(flag2){
if(str[p3]==str[p4]&&ck[str[p3]]) p3--,p4++;
else flag2=0;
}
if(p1<1||p2>len) flag1=0;
if(p3<1||p4>len) flag2=0;
if(flag1==0&&flag2==0) break;
}
p1++;p2--;
p3++;p4--;
return max(p2-p1+1,p4-p3+1);
}
void solve(){
scanf("%s",str+1);
len=strlen(str+1);
int ans=0;
rep(i,1,len) ans=max(ans,check(i));
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
ck['A']=1;ck['H']=1;ck['I']=1;ck['M']=1;ck['O']=1;ck['T']=1;ck['U']=1;
ck['V']=1;ck['W']=1;ck['X']=1;ck['Y']=1;
while(T--) solve();
}
J. Lazy Physics Cat
time limit per test1.0 s memory limit per test256 MB
Physics cat likes to draw shapes and figure out their area. He starts by drawing a circle. Then inside the circle, he draws the triangle X, Y, Z - where Y is the center point of the circle, and X and Z touch the circumference of the circle. Please note that points X and Yalways have the same x-coordinate.
Given L (the distance between Points X and Y) and A (the angle XYZ in degrees); help physics cat find the shaded area between the right side of the triangle and the circumference of the circle. And when we say help, we mean do all the work for him.Input
The first line of input is T – the number of test cases.
The first line of each test case is integers L and A (1 ≤ L ≤ 1000) (1 ≤ A ≤ 180).Output
For each test case, output on a line the area of the shaded region rounded to 6 decimal places.
Exampleinput
3 1 90 2 180 10 30
output
0.285398
6.283185
1.179939
简单几何题
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
const double pi=acos(-1.0);
double a,r,l;
void solve(){
scanf("%lf%lf",&r,&a);
l=2.0*r*sin(a/2/360*2*pi);
double s1=pi*r*r*a/360.0;
double s2;
double h=r*cos(a/2/360*2*pi);
s2=l*h/2.0;
printf("%.6lf\n",s1-s2);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
K. Owl Geeks
time limit per test1.0 s memory limit per test256 MB
The owls have the following equation:
Y = a × x2 + b × x
With a, b, and N given, they decide to put into a set the integer values of Y that are less than or equal to N and that are outputted from the equation from any positive integer x.
With that set of numbers, they come up with the problem of finding the winning digit among them.
The winning digit is a digit from 0 to 9 that will get the maximum number of points. How are points for a digit calculated you may ask? Well, be a bit more patient, I’m going to tell you now.
For each number in the set, if the digit was the most repeated digit or tied with other digits as the most repeated digit in the ith number of set S, then it would get one point from that ith number.
Can you tell the owls what the winning digit is?Input
The first line of input is T – the number of test cases.
The first line of each test case is a, b, and N (1 ≤ a, b, N ≤ 105).Output
For each test case, print on a line the winning digit with the maximum number of points. If there is a tie, print the minimum digit among them. If the set is empty, print - 1.
Exampleinput
2 1 2 50 20 3 10
output
3
-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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,a,b,ans[10];
void check(int x){
int num[10]={0,};
while(x){
num[x%10]++;
x/=10;
}
int maxx=0;
rep(i,0,9) if(num[i]>maxx){
maxx=num[i];
}
rep(i,0,9) if(num[i]==maxx) ans[i]++;
}
void solve(){
scanf("%d%d%d",&a,&b,&n);
set<int> s;
rep(i,0,9) ans[i]=0;
int x=1;
while(1){
int k=a*x*x+b*x;
if(k>n) break;
else x++,s.insert(k);
}
if(s.empty()) {puts("-1");return;}
for(auto u:s) check(u);
int maxx=0,res=0;
rep(i,0,9) if(ans[i]>maxx){
maxx=ans[i];
res=i;
}
printf("%d\n",res);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
M. Make Cents?
time limit per test6.0 s memory limit per test256 MB
Every year, an elephant qualifies to the Arab Collegiate Programming Competition. He graduated this year, but that’s irrelephant. What’s important is that the location of the competition might not have been the same every year. Therefore, after every trip, he always has leftover money in the currency of the country he visited.
Now he wants to see how much Jordanian Dinars he has after all those competitions. Can you help him convert the leftover money from all competitions to Jordanian Dinar, if that makes any cents?Input
The first line of input is T – the number of test cases.
The first line of each test case contains C and N (1 ≤ C, N ≤ 100000), the number of currency types and the number of competitions, respectively.
The next C lines each contain the name of the currency Ci of maximum length 10 in lowercase and/or uppercase letters, and the value Vi of that currency in Jordanian Dinar (0 < Vi ≤ 1000). The names are case-sensitive.
The next N lines each contains an amount left over from each competition (0 ≤ Ni ≤ 1000), and the name of the currency of that amount (it is guaranteed that the name was either given in the input or is “JD”).Output
For each test case, print on a single line the total amount of money he has in Jordanian Dinar(JD) rounded to 6 decimal digits.
Exampleinput
1 3 5 dollar 0.71 euro 0.76 turkish 0.17 5.1 dollar 6 dollar 7 turkish 3 euro 1.1 JD
output
12.451000
傻逼题，但是要注意cin会tle，用scanf
#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)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int c,n;
char s[12];
void solve(){
scanf("%d%d",&c,&n);
map<string,double> mp;
mp["JD"]=1;
rep(i,1,c){
double k;
scanf("%s%lf",s,&k);
string t=s;
mp[t]=k;
}
double ans=0;
rep(i,1,n){
double k;
scanf("%lf%s",&k,s);
string t=s;
ans+=k*mp[t];
}
printf("%.6lf\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
