Codeforces Round #567 (Div. 2)

c题FST了,又是艰难上分的一场,期末考试搞得我根本没时间打题了


A. Chunga-Changa

time limit per test1 second memory limit per test512 megabytes

Soon after the Chunga-Changa island was discovered, it started to acquire some forms of civilization and even market economy. A new currency arose, colloquially called “chizhik”. One has to pay in chizhiks to buy a coconut now.

Sasha and Masha are about to buy some coconuts which are sold at price 𝑧z chizhiks per coconut. Sasha has 𝑥x chizhiks, Masha has 𝑦ychizhiks. Each girl will buy as many coconuts as she can using only her money. This way each girl will buy an integer non-negative number of coconuts.

The girls discussed their plans and found that the total number of coconuts they buy can increase (or decrease) if one of them gives several chizhiks to the other girl. The chizhiks can’t be split in parts, so the girls can only exchange with integer number of chizhiks.

Consider the following example. Suppose Sasha has 55 chizhiks, Masha has 44 chizhiks, and the price for one coconut be 33 chizhiks. If the girls don’t exchange with chizhiks, they will buy 1+1=21+1=2 coconuts. However, if, for example, Masha gives Sasha one chizhik, then Sasha will have 66 chizhiks, Masha will have 33 chizhiks, and the girls will buy 2+1=32+1=3 coconuts.

It is not that easy to live on the island now, so Sasha and Mash want to exchange with chizhiks in such a way that they will buy the maximum possible number of coconuts. Nobody wants to have a debt, so among all possible ways to buy the maximum possible number of coconuts find such a way that minimizes the number of chizhiks one girl gives to the other (it is not important who will be the person giving the chizhiks).Input

The first line contains three integers 𝑥x, 𝑦y and 𝑧z (0≤𝑥,𝑦≤10180≤x,y≤1018, 1≤𝑧≤10181≤z≤1018) — the number of chizhics Sasha has, the number of chizhics Masha has and the price of a coconut.Output

Print two integers: the maximum possible number of coconuts the girls can buy and the minimum number of chizhiks one girl has to give to the other.
Examplesinput

5 4 3

output

3 1

input

6 8 2

output

7 0

Note

The first example is described in the statement. In the second example the optimal solution is to dot exchange any chizhiks. The girls will buy 3+4=73+4=7 coconuts.

傻逼签到题搞了一发罚时,真是气死了,恨自己蠢啊

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(int)2e5+100;
const ll INF=(ll)1e18;
ll a,b,c;
int main(){
	cin>>a>>b>>c;
	ll ans=(a+b)/c;
	a%=c;b%=c;
	ll re=0;
	if(a+b>=c) re=min(c-a,c-b);
	printf("%lld %lld\n",ans,re);
}


B. Split a Number

time limit per test2 seconds memory limit per test512 megabytes

Dima worked all day and wrote down on a long paper strip his favorite number 𝑛n consisting of 𝑙l digits. Unfortunately, the strip turned out to be so long that it didn’t fit in the Dima’s bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.Input

The first line contains a single integer 𝑙l (2≤𝑙≤1000002≤l≤100000) — the length of the Dima’s favorite number.

The second line contains the positive integer 𝑛n initially written on the strip: the Dima’s favorite number.

The integer 𝑛n consists of exactly 𝑙l digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.Output

Print a single integer — the smallest number Dima can obtain.
Examplesinput

7
1234567

output

1801

input

3
101

output

11

Note

In the first example Dima can split the number 12345671234567 into integers 12341234 and 567567. Their sum is 18011801.

In the second example Dima can split the number 101101 into integers 1010 and 11. Their sum is 1111. Note that it is impossible to split the strip into “1” and “01” since the numbers can’t start with zeros.

大数水题,从中间往前找一个数,往后找一个数比一比就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(int)1e5+100;
const ll INF=(ll)1e18;
int n;
string str;
struct bign{
    int d[maxn];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }
};
bign change(string str){
    bign a;
    a.len=str.length();
    for(int i=0;i<a.len;i++){
        a.d[i]=str[a.len-i-1]-'0';
    }
    return a;
}
int compare(bign a,bign b){
    if(a.len>b.len)return 1;//a大于b
    else if(a.len<b.len)return -1;//a<b
    else{
        for(int i=a.len-1;i>=0;i--){
            if(a.d[i]>b.d[i])return 1;
            else if(a.d[i]<b.d[i])return -1;
        }
        return 0;//两个数相等
    }
}
bign add(bign a,bign b){
    bign c;
    int carry=0;
    for(int i=0;i<a.len||i<b.len;i++){
        int temp=a.d[i]+b.d[i]+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    if(carry!=0){
        c.d[c.len++] =carry;
    }
    return c;
}
void print(bign a){
    for(int i=a.len-1;i>=0;i--) printf("%d",a.d[i]);
}
int main(){
	cin>>n>>str;
	bign ans;
	int pos1=n/2+1;int pos2=n/2;
	while(pos1--){
		if(str[pos1]=='0') continue;
		bign a=change(str.substr(0,pos1));
		bign b=change(str.substr(pos1));
		ans=add(a,b);
		break;
	}
	while(pos2++<str.length()){
		if(str[pos2]=='0') continue;
		bign c=change(str.substr(0,pos2));
		bign d=change(str.substr(pos2));
		bign tt=add(c,d);
		if(compare(ans,tt)==1) ans=tt;
		break;
	}
	print(ans);
}


C. Flag

time limit per test2 seconds memory limit per test512 megabytes

Innokenty works at a flea market and sells some random stuff rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in 𝑛⋅𝑚n⋅m colored pieces that form a rectangle with 𝑛n rows and 𝑚m columns.

The colored pieces attracted Innokenty’s attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of equal heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.

Innokenty has not yet decided what part he will cut out, but he is sure that the flag’s boundaries should go along grid lines. Also, Innokenty won’t rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different.

These subrectangles are flags.

These subrectangles are not flags.Input

The first line contains two integers 𝑛n and 𝑚m (1≤𝑛,𝑚≤10001≤n,m≤1000) — the number of rows and the number of columns on the blanket.

Each of the next 𝑛n lines contains 𝑚m lowercase English letters from ‘a’ to ‘z’ and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.Output

In the only line print the number of subrectangles which form valid flags.
Examplesinput

4 3
aaa
bbb
ccb
ddd

output

6

input

6 1
a
a
b
b
c
c

output

1

Note

The selected subrectangles are flags in the first example.

首先预处理出两个数组down和suf表示i,j这个位置的连续后缀和连续下缀的最大长度,然后再n^2枚举每个点,若这个点下面两个不同的点能组成flag,那么维护一下这个flag的最小长度,显然答案加上 l*(l+1)/2 ,然后往后跳l格继续比较

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e3+100;
int n,m;
char mp[maxn][maxn];
int down[maxn][maxn],suf[maxn][maxn];
int main(){
	cin>>n>>m;
	rep(i,1,n) scanf("%s",mp[i]+1);
	dep(i,n,1) dep(j,m,1){
		if(mp[i][j]==mp[i][j+1]) suf[i][j]=suf[i][j+1]+1;
		if(mp[i][j]==mp[i+1][j]) down[i][j]=down[i+1][j]+1;
	}
	int ans=0;
	rep(i,1,n) rep(j,1,m) {
		int a=i,b=a+down[a][j]+1;
		if(b>=n||b+down[b][j]+1>n) continue;
		int c=b+down[b][j]+1,d=c+down[c][j]+1;
		if(b-a!=c-b||c-b>d-c) continue;
		int h=b-a,l=maxn;
		rep(t,a,a+h*3-1) l=min(l,suf[t][j]+1);
		ans+=l*(l+1)/2;
		j=j+l-1;
	}
	printf("%d\n",ans);
}


D. Irrigation

time limit per test2.5 seconds memory limit per test512 megabytes

Misha was interested in water delivery from childhood. That’s why his mother sent him to the annual Innovative Olympiad in Irrigation (IOI). Pupils from all Berland compete there demonstrating their skills in watering. It is extremely expensive to host such an olympiad, so after the first 𝑛n olympiads the organizers introduced the following rule of the host city selection.

The host cities of the olympiads are selected in the following way. There are 𝑚m cities in Berland wishing to host the olympiad, they are numbered from 11 to 𝑚m. The host city of each next olympiad is determined as the city that hosted the olympiad the smallest number of times before. If there are several such cities, the city with the smallest index is selected among them.

Misha’s mother is interested where the olympiad will be held in some specific years. The only information she knows is the above selection rule and the host cities of the first 𝑛n olympiads. Help her and if you succeed, she will ask Misha to avoid flooding your house.Input

The first line contains three integers 𝑛n, 𝑚m and 𝑞q (1≤𝑛,𝑚,𝑞≤5000001≤n,m,q≤500000) — the number of olympiads before the rule was introduced, the number of cities in Berland wishing to host the olympiad, and the number of years Misha’s mother is interested in, respectively.

The next line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤𝑚1≤ai≤m), where 𝑎𝑖ai denotes the city which hosted the olympiad in the 𝑖i-th year. Note that before the rule was introduced the host city was chosen arbitrarily.

Each of the next 𝑞q lines contains an integer 𝑘𝑖ki (𝑛+1≤𝑘𝑖≤1018n+1≤ki≤1018) — the year number Misha’s mother is interested in host city in.Output

Print 𝑞q integers. The 𝑖i-th of them should be the city the olympiad will be hosted in the year 𝑘𝑖ki.
Examplesinput

6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16

output

4
3
4
2
3
4
1
2
3
4

input

4 5 4
4 4 5 1
15
9
13
6

output

5
3
3
3

Note

In the first example Misha’s mother is interested in the first 1010 years after the rule was introduced. The host cities these years are 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

In the second example the host cities after the new city is introduced are 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1.

线段树加二分好题 ,好吧这是道傻逼题,是我自己蠢了没想到。

其实很容易想到,每次填数字都是一个循环节重复k次,而每个循环节长度和循环次数都是可以预处理出来的;

对于每个询问,显然我们可以离线处理,让询问升序,这样后面的询问中循环节的元素必然包含之前的,考虑用树状数组维护一个权值数组,每次查询第k大;

那么代码就很好写了,首先预处理出来每一年循环节中所有元素的个数(显然是当前循环节长度*循环次数),那么对于每个询问,我们只要二分出第一个大于等于的长度然后将没有出现的城市添加到树状数组里再查询第k大就好了(当然主席树也是可以做的,甚至不用离线)

权值树状数组+二分

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(int)5e5+100;
const ll INF=(ll)1e18;
int bef,cityNum,qNum,c[maxn],a[maxn],ans[maxn],cnt=0;
vector<pii> vec;
ll pre[maxn];
pair<ll,int> q[maxn];
int lowbit(int x){return x&(-x);}
void modify(int pos,int val){
    for(int i = pos;i<maxn;i+=lowbit(i)) c[i]+=val;
}
int find_kth(int k){
    int ans=0,sum=0;
    for(int i=log2(maxn);i>=0;i--){
        if(ans+(1<<i)<maxn&&sum+c[ans+(1<<i)]<k){
            ans+=1<<i;
            sum+=c[ans];
        }
    }
    return ans+1;
}
int main(){
	cin>>bef>>cityNum>>qNum;
	rep(i,1,bef) {int x;scanf("%d",&x);a[x]++;}
	rep(i,1,cityNum) vec.pb({a[i],i});
	sort(vec.begin(),vec.end()); 
	rep(i,1,qNum) scanf("%lld",&q[i].F),q[i].F-=bef,q[i].S=i;
	sort(q+1,q+1+qNum);
	rep(i,0,cityNum-2){
		pre[i]+=1ll*(vec[i+1].F-vec[i].F)*(i+1);
		pre[i+1]=pre[i];
	}
	rep(i,1,qNum){
		int pos=lower_bound(pre,pre+cityNum-1,q[i].F)-pre;
		if(pos) q[i].F-=pre[pos-1];
		//printf("%d\n",q[i].F);
		while(cnt<(int)vec.size()&&cnt<pos+1) modify(vec[cnt++].S,1);
		int rk=(q[i].F-1)%(pos+1)+1;
		ans[q[i].S]=find_kth(rk);
	}
	rep(i,1,qNum) printf("%d\n",ans[i]);
}


实际上这道题并不用这么复杂,我们考虑对于之前给出的n年的信息,对于第一个样例,首先假设一开始n为0

1,2,3,4 | 1,2,3,4 | 1, 2, 3, 4
1,2,3,4 | 5,6,7,8 | 9,10,11,12

上面是每一年的举办城市,下面的对应的年份

👆这样的一个关系是很好理解的,那么现在给出了n年的信息,上图也就变成了这样:

1,2,3,4 | 1,2,3,4 | 1, 2, 3, 4
123,4 | 56,7,8 | 9,10,11,12
举办1次 | 举办2次 | 举办3次

加粗的是样例给出的举办城市对应的本来应该要举办的年份
对于城市1,它应该在1,5,9这三年举办
对于城市2,它应该在2,6,10这三年举办
…………

那么显然,对于第9年之后的年份,得到的答案都是1,2,3,4的循环节,显然(t-1)%m+1就是答案;

那么现在9之前还有三个数没有填上,这三个数(4,7,8)就是对应的7,8,9三年的答案(要%m,理解就好)

对于这个问题,之前某场教育场有一道很类似的题目,就只要维护1-n这n年中每一年之前的年份中空位的数量就可以了,类似于维护了一个前缀和,这道题中因为是1-n排序的,所以直接对于每个位置减去这个位置本来应该有的值就是空位的数量了,对应代码是rep(i,1,n) a[i]-=i;

这时候,对于一个询问,二分一下第一次出现这个空位的下标就表示了在这个数之前已经有多少数填好了,那么就直接t+=lower_bound(a+1,a+1+n,t)-a-1;

正解

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)5e5+100;
ll cnt[maxn],a[maxn];
int n,m,q,x;
int main(){
	cin>>n>>m>>q;
	rep(i,1,n) {scanf("%d",&x);a[i]=(cnt[x]++)*m+x;}
	sort(a+1,a+1+n);
	rep(i,1,n) a[i]-=i;
	while(q--){
		ll t;scanf("%lld",&t); t-=n;
		if(t>a[n]) t+=n;
		else t+=lower_bound(a+1,a+1+n,t)-a-1;
		printf("%lld\n",(t-1)%m+1);
	}
}

发表评论,支持MarkDown语法