2018湘潭市赛暨全国邀请赛（湖南）

湘潭市赛暨全国邀请赛（湖南）"/>

2018湘潭市赛暨全国邀请赛（湖南）

A Easy h-index
比赛题目：
.pdf

The h-index of an author is the largest h where he has at least h papers with citations not less than h.

Bobo has published many papers.
Given a0,a1,a2,…,an which means Bobo has published ai papers with citations exactly i, find the h-index of Bobo.

Input
The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains (n+1) integers a0,a1,…,an.

Output
For each test case, print an integer which denotes the result.

Constraint

• 1≤n≤2⋅105
• 0≤ai≤109
• The sum of n does not exceed 250,000.

Sample Input
1
1 2
2
1 2 3
3
0 0 0 0

Sample Output
1
2
0

思路：后缀和
代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 2e5+5;ll a[N];
int main() {int n;while(cin>>n) {for(int i=0; i<=n; i++)cin>>a[i];int ans;ll sum=0;for(int i=n+1; i>=0&&sum<i; ) {sum+=a[--i];ans=i;}cout<<ans<<endl;}return 0;
}

B Higher h-index

Problem Description
The h-index of an author is the largest h where he has at least h papers with citations not less than h.

Bobo has no papers and he is going to publish some subsequently.
If he works on a paper for x hours, the paper will get (a⋅x) citations, where a is a known constant.
It’s clear that x should be a positive integer.
There is also a trick – one can cite his own papers published earlier.

Given Bobo has n working hours, find the maximum h-index of him.

Input
The input consists of several test cases and is terminated by end-of-file.

Each test case contains two integers n and a.

Output
For each test case, print an integer which denotes the maximum h-index.

Constraint

• 1≤n≤109
• 0≤a≤n
• The number of test cases does not exceed 104.

Sample Input
3 0
3 1
1000000000 1000000000

Sample Output
1
2
1000000000

Hint

For the first sample, Bobo can work 3 3 $3$ papers for 1" role="presentation" style="position: relative;">11$1$ hour each.
With the trick mentioned, he will get papers with citations 2,1,0 2 , 1 , 0 $2, 1, 0$. Thus, his h h $h$-index is 1" role="presentation" style="position: relative;">11$1$.

For the second sample, Bobo can work 2 2 $2$ papers for 1" role="presentation" style="position: relative;">11$1$ and 2 2 $2$ hours respectively. He will get papers with citations 1+1,2+0" role="presentation" style="position: relative;">1+1,2+01+1,2+0$1 + 1, 2 + 0$. Thus, his h h $h$-index is 2" role="presentation" style="position: relative;">22$2$.

思路：比赛的时候没看这题。。 赛后正解就是一个结论。 (n+a)/2向下取整

Problem Description
Bobo has n tuples (a1,b1,c1),(a2,b2,c2),…,(an,bn,cn).
He would like to find the lexicographically smallest permutation p1,p2,…,pn of 1,2,…,n such that for i∈{2,3,…,n} it holds that
api−1+bpi−1api−1+bpi−1+cpi−1≤api+bpiapi+bpi+cpi.

Input
The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The i-th of the following n lines contains 3 integers ai, bi and ci.

Output
For each test case, print n integers p1,p2,…,pn seperated by spaces.
DO NOT print trailing spaces.

Constraint

• 1≤n≤103
• 1≤ai,bi,ci≤2×109
• The sum of n does not exceed 104.

Sample Input
2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

Sample Output
2 1
1 2
1 2 3

思路：
现场赛时就直接计算，然后用double比较大小排序了，但是这里用double表示不了
然后就转化所给的式子，交叉相乘化简。

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3+5;struct Node {int id;ll a,b,c;
} p[N];
bool cmp(Node x,Node y) {ull tmp1=x.a*y.c+x.b*y.c;ull tmp2=y.a*x.c+y.b*x.c;if(tmp1!=tmp2)return tmp1<tmp2;return x.id<y.id;
}
int main() {int n;while(~scanf("%d",&n)) {for(int i=0; i<n; i++) {scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c);p[i].id=i+1;}sort(p,p+n,cmp);for(int i=0; i<n-1; i++) {printf("%d ",p[i].id);}printf("%d\n",p[n-1].id);}return 0;
}

G String Transformation
Problem Description
Bobo has a string S=s1s2…sn consists of letter a, b and c.
He can transform the string by inserting or deleting substrings aa, bb and abab.

Formally, A=u∘w∘v (“∘” denotes string concatenation) can be transformed into A′=u∘v and vice versa where u, v are (possibly empty) strings and w∈{aa,bb,abab}.

Given the target string T=t1t2…tm, determine if Bobo can transform the string S into T.

Input
The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains a string s1s2…sn.
The second line contains a string t1t2…tm.

Output
For each test case, print Yes if Bobo can. Print No otherwise.

Constraint

• 1≤n,m≤104
• s1,s2,…,sn,t1,t2,…,tm∈{a,b,c}
• The sum of n and m does not exceed 250,000.

Sample Input
ab
ba
ac
ca
a
ab

Sample Output
Yes
No
No

Hint

For the first sample, Bobo can transform as ab => aababb => babb => ba.

思路：
找c的个数，若c的个数不相等，直接输出No；反之，就按照c的位置划分，比较a,b的个数的奇偶性, 只有奇偶性都相同时输出Yes，否则输出No

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3+5;bool check(int a,int aa,int b,int bb) {if(a%2!=aa%2||b%2!=bb%2)return true;return false;
}
int main() {string s,t;while(cin>>s>>t) {int sz1=s.size();int sz2=t.size();int cnt1c=0,cnt2c=0;for(int i=0; i<sz1; i++) {if(s[i]=='c')cnt1c++;}for(int i=0; i<sz2; i++) {if(t[i]=='c')cnt2c++;}// printf("cnt1c=%d cnt2c=%d\n",cnt1c,cnt2c);if(cnt1c!=cnt2c)cout<<"No";else if(cnt1c==cnt2c&&!cnt2c) {int acnt=0,aacnt=0;int bcnt=0,bbcnt=0;for(int i=0; i<sz1; i++) {if(s[i]=='a')acnt++;elsebcnt++;}for(int i=0; i<sz2; i++) {if(t[i]=='a')aacnt++;elsebbcnt++;}if(check(acnt,aacnt,bcnt,bbcnt)) {cout<<"No";} elsecout<<"Yes";} else {bool flag=0;int acnt=0,aacnt=0;int bcnt=0,bbcnt=0;int i,j,k;for(i=0,j=0; i<sz1; i++) {if(s[i]=='c') {for(k=j; k<sz2&&t[k]!='c'; k++) {if(t[k]=='a')aacnt++;elsebbcnt++;}if(check(acnt,aacnt,bcnt,bbcnt)) {flag=1;break;}j=k+1;} else {if(s[i]=='a')acnt++;elsebcnt++;}}for(int i=j; i<sz2; i++) {if(t[i]=='a')aacnt++;elsebbcnt++;}if(check(acnt,aacnt,bcnt,bbcnt)) {flag=1;}if(!flag)cout<<"Yes";elsecout<<"No";}cout<<endl;}return 0;
}

K 2018
Problem Description
Given a,b,c,d, find out the number of pairs of integers (x,y) where a≤x≤b,c≤y≤d and x⋅y is a multiple of 2018.

Input
The input consists of several test cases and is terminated by end-of-file.

Each test case contains four integers a,b,c,d.

Output
For each test case, print an integer which denotes the result.

Constraint

• 1≤a≤b≤109,1≤c≤d≤109
• The number of tests cases does not exceed 104.

Sample Input
1 2 1 2018
1 2018 1 2018
1 1000000000 1 1000000000

Sample Output
3
6051
1485883320325200

思路：
这道题和12届湖南省赛的2016这道题很像，然后就直接按那个思路写了半天，现场比较懵，就没想到直接找因子计算
2018的因子有1，2，1009，2018，计算四次得到答案

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3+5;ll cal(int x,int y,int d) {ll ans=y/d-(x-1)/d;return ans;
}
int main() {int a,b,c,d;while(~scanf("%d%d%d%d",&a,&b,&c,&d)) {ll t1=cal(a,b,2);ll t2=cal(a,b,1009);ll t3=cal(a,b,2018);ll t4=cal(c,d,2);ll t5=cal(c,d,1009);ll t6=cal(c,d,2018);ll ans1=(t2-t3)*t4; /// [0,a)中1009的奇数倍的个数 * [c,d]中偶数个数ll ans2=t3*(d-c+1); /// [a,b]中2018的倍数个数 * [c,d]中所有数个数ll ans3=(t5-t6)*(t1-t3);/// [a,b]中偶数个数 * [c,d]中1009奇数倍的个数 ，去掉已经计算过的2018ll ans4=t6*(b-a+1-t2);/// [a,b]中所有数个数 * [c,d]中2018的倍数个数 ，去掉已经计算过的1009printf("%lld\n",ans1+ans2+ans3+ans4);}return 0;
}