[Codeforces] Round #352 (Div. 2)

人生不止眼前的狗血,还有远方的狗带

A题B题一如既往的丝帛题

A题题意:询问按照12345678910111213...的顺序排列下去第n(n<=10^3)个数是多少

题解:打表,输出

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dig[10],A[1005];
 4 int main(){
 5     int aa=0;
 6     for(int i=1;;i++){
 7         int x=i,dd=0;
 8         while(x)dig[++dd]=x%10,x/=10;
 9         for(int j=dd;j;j--)
10             A[++aa]=dig[j];
11         if(aa>=1000)break;
12     }
13     int n;
14     scanf("%d",&n);
15     printf("%d\n",A[n]);
16     return 0;
17 }

B题题意:对于一个由小写字母组成的字符串s(|s|<=10^5),每次可以把一个字母改写成任意一个字母,

     求使得这个序列没有重复子串的最小操作次数,若不存在输出-1

题解:因为单个字母也是子串,所以问题即为把一个字符串全部改成不同字母的最少步数

   因为只有26个字母,所以若|s|>26则输出-1,否tong[i]表示第i个字母出现了几次,ans=sigma(max(tong[i]-1,0))

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,tong[26];
 4 char s[100005];
 5 int main(){
 6     scanf("%d%s",&n,s);
 7     if(n>26)puts("-1");
 8     else{
 9         for(int i=0;i<n;i++)
10             tong[s[i]-‘a‘]++;
11         int ans=0;
12         for(int i=0;i<26;i++)
13             if(tong[i])ans+=tong[i]-1;
14         printf("%d\n",ans);
15     }
16     return 0;
17 }

C题思路很简单,然而细节狗带

C题题意:二维平面上有n个(n<=10^5)点(xi,yi),有两个起点A(ax,ay)和B(bx,by),一个终点T(tx,ty)(0<=横纵坐标<=10^9)

     可以从两个起点中的一个或两个出发,经过所有(xi,yi),且每到达一个(xi,yi)都要回到终点,问所有走过距离的最小值

题解:其实使距离改变的只有最开始的经过的第一个的点,及经过该点的方式

   对于每个点,我们计算到T的距离tdi,到A的距离adi,和到B的距离bdi

   然后把make_pair(adi-tdi,i),和make_pair(bdi-tdi,i)分别放到两个数组里排序

   表示从A点或B点直接到达第一个点然后回到T使总距离减小了adi-tai或bdi-tai

   然后就是分类讨论,细节见代码QwQ

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define mp make_pair
 5 #define fir first
 6 #define sec second
 7 vector<pair<double,int> >haha[2];
 8 double x[3],y[3],tmp[3];
 9 double sq(double a){ return a*a; }
10 double pdd(double x1,double y1,double x2,double y2){
11     return sqrt(sq(x1-x2)+sq(y1-y2));
12 }
13 int main(){
14     for(int i=0;i<3;i++)
15         scanf("%lf%lf",&x[i],&y[i]);
16     int n;
17     scanf("%d",&n);
18     double ans=0,xx,yy;
19     for(int i=1;i<=n;i++){
20         scanf("%lf%lf",&xx,&yy);
21         for(int j=0;j<3;j++)
22             tmp[j]=pdd(x[j],y[j],xx,yy);
23         for(int j=0;j<2;j++)
24             haha[j].pb(mp(tmp[j]-tmp[2],i));
25         ans+=tmp[2]*2;
26     }
27     for(int i=0;i<2;i++)
28         sort(haha[i].begin(),haha[i].end());
29     if(haha[0][0].fir<0&&haha[1][0].fir<0){
30         double Min;
31         if(haha[0][0].sec==haha[1][0].sec)
32             Min=min(haha[0][0].fir+min(0.0,haha[1][1].fir),min(0.0,haha[0][1].fir)+haha[1][0].fir);
33         else Min=haha[0][0].fir+haha[1][0].fir;
34         printf("%.12lf\n",ans+Min);
35     }
36     else printf("%.12lf\n",ans+min(haha[0][0].fir,haha[1][0].fir));
37     return 0;
38 }

刀题懵逼,没有想到最关键的地方

刀题题意:给定一个长度为n(n<=5*10^5)的序列,每次操作把最大值-1,最小值+1,有多个则随机选一个中

     求k(k<=10^9)次操作之后序列最大值与最小值的差

题解:真-最关键的地方:可以把最大值-1和最小值+1操作分开做

   然后就没有然后了

 1 By Ngshily_, contest: Codeforces Round #352 (Div. 1), problem: (B) Robin Hood, Accepted, #
 2
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 typedef long long ll;
 6 #define maxn 500005
 7 int n;
 8 ll k,c[maxn];
 9 void solve(){
10     sort(c+1,c+1+n);
11     ll tmp=k,lst=c[n];
12     for(int i=2;i<=n;i++){
13         ll delt=(c[i]-c[i-1])*(i-1);
14         if(delt<=tmp)tmp-=delt;
15         else{ lst=c[i-1]; break; }
16     }
17     int pos=0;
18     while(pos+1<=n&&c[pos+1]<=lst)pos++;
19     int shang=tmp/pos,yu=tmp%pos;
20     for(int i=1;i<=pos;i++)
21         c[i]=lst+shang+(i<=yu);
22 }
23 int main(){
24     scanf("%d%I64d",&n,&k);
25     for(int i=1;i<=n;i++)
26         scanf("%I64d",&c[i]);
27     solve();
28     for(int i=1;i<=n;i++)c[i]=-c[i];
29     solve();
30     sort(c+1,c+1+n);
31     printf("%I64d\n",c[n]-c[1]);
32     return 0;
33 }

E题题意:给定一个长度为n(n<=2*10^5)的序列A(ai<=2*10^5),设f[i][j]表示去掉[i,j]中的元素的序列中两数gcd的最大值,

     求sigma(sigma(f[i][j]))

     若我们求出了H[i]表示gcd<i的序列的个数,就可以轻易了www

      要求H数组我们可以从大到小枚举一个divsor,通过如下方法求出H[divsor]

       设next[i]表示对于任意j>=next[i],f[i][j]<divsor的最小位置,即后面的值随便取都不会使f[i][j]>divsor

       H[divsor]=sigma(n-next[i]+1)

     然后我们需要考虑divsor到divsor-1时next数组的转移

     首先预处理出pos数组,pos[i]表示包含i这个因子的数在序列中的位置的集合

     假设pos[divsor-1]={p1,p2,p3...pk-1,pk}

     显然我们保留的区间最多只能包含其中的一个数,则...分类讨论again,都是套路

     用线段树维护next数组

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson rt<<1,l,mid
 4 #define rson rt<<1|1,mid+1,r
 5 typedef long long ll;
 6 #define maxn 200005
 7 ll sum[maxn<<2],mn[maxn<<2],mx[maxn<<2],cvr[maxn<<2],H[maxn];
 8 int n,A[maxn],L[maxn][2],R[maxn][2];
 9 void push_up(int rt){
10     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
11     mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
12     mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
13 }
14 void push_now(int rt,int len,ll val){
15     sum[rt]=val*len;
16     mn[rt]=mx[rt]=cvr[rt]=val;
17 }
18 void push_down(int rt,int l,int mid,int r){
19     if(cvr[rt]){
20         push_now(rt<<1,mid-l+1,cvr[rt]);
21         push_now(rt<<1|1,r-mid,cvr[rt]);
22         cvr[rt]=0;
23     }
24 }
25 void update(int rt,int l,int r,int ql,int qr,ll val){
26     if(ql>r||qr<l||mn[rt]>val)return;
27     if(ql<=l&&qr>=r&&mx[rt]<=val){
28         push_now(rt,r-l+1,val);
29         return;
30     }
31     int mid=(l+r)>>1;
32     push_down(rt,l,mid,r);
33     if(ql<=mid)update(lson,ql,qr,val);
34     if(qr>mid)update(rson,ql,qr,val);
35     push_up(rt);
36 }
37 int main(){
38     scanf("%d",&n);
39     int Max=0;
40     for(int i=1;i<=n;i++){
41         scanf("%d",&A[i]);
42         Max=max(Max,A[i]);
43         int x=sqrt(A[i]);
44         for(int j=1;j<=x;j++){
45             if(A[i]%j==0){
46                 if(!L[j][0])L[j][0]=i;
47                 else if(!L[j][1])L[j][1]=i;
48                 R[j][1]=R[j][0],R[j][0]=i;
49                 if(j*j!=A[i]){
50                     if(!L[A[i]/j][0])L[A[i]/j][0]=i;
51                     else if(!L[A[i]/j][1])L[A[i]/j][1]=i;
52                     R[A[i]/j][1]=R[A[i]/j][0],R[A[i]/j][0]=i;
53                 }
54             }
55         }
56     }
57     for(int i=1;i<=n;i++)
58         update(1,1,n,i,i,i);
59     for(int i=Max+1;i;i--){
60         if(L[i][0]!=R[i][0]){
61             update(1,1,n,1,L[i][0],R[i][1]);
62             update(1,1,n,L[i][0]+1,L[i][1],R[i][0]);
63             update(1,1,n,L[i][1]+1,n,n+1);
64         }
65             H[i]=(ll)n*(n+1)-sum[1];
66     }
67     ll ans=0;
68     for(int i=1;i<=Max;i++)
69         ans+=(H[i+1]-H[i])*i;
70     printf("%I64d\n",ans);
71     return 0;
72 }

    就是这样,没有喵          

时间: 05-13

[Codeforces] Round #352 (Div. 2)的相关文章

Codeforces Round #352 (Div. 2) D. Robin Hood

题目连接请戳此处 题意:n个人每人有一定的财富值ci,每天Robin Hood从最富的人手中取财富1分给最穷的人(取后最穷, 即可以退回),若有多个最穷的人,任选一个给出财富值.问k天后最富的人和最穷的人财富差值为多少. 1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109 1 ≤ ci ≤ 109 分析: 每一天随着财富值的取和给,最穷的人和最富的人都在动态更新. 最后要求的是  (richest-poorest)min,那么  要使这个等式最小,只需求出k天后richest的最小值和po

Codeforces Round #352 (Div. 2) C. Recycling Bottles(枚举)

思路:分析完这道题后会发现  当两个人捡到第一个瓶子后, 之后走的路的最小值都是不会变的了. 所以只要找出两个走到各自的第一个瓶子是最小值的情况的时候(其中还有一个人不走,一个人走的情况).   如果当有两个人或有一个人到其第一个瓶子的权值大于瓶子到回收点时,选取权值小的那个. 而且计算最小值的时候 只需取出两个权值数组中最小的两个数 即可 不用全部遍历来选取. #include<iostream> #include<cstdio> #include<cmath> #i

Codeforces Round #352 (Div. 2) D. Robin Hood (二分法+判断平衡态)

解题思路: 由求最小值和求最大值各自二分. 由l*(a[l+1]-a[l]):求取填 1~l 到a[l+1]的高度需要多少的钱,如果大于剩余的k 则可执行 若否 判断剩余的k是否为l,若否最小值为a[l],否则 为a[l]+k/l; 由(n-r+1)*(a[r]-a[r-1]):求去掉n~n-r+1的这部分需要多少钱,如果大于剩余的k 则执行 若否 判断剩余的k是否为n-r+1,若是最大值为a[n-r+1]-k/(n-r+1); 如果最大值小于最大值,直接printf 如果最小值大于等于最大值,

Codeforces Round #352 (Div. 2) B - Different is Good

A wise man told Kerem "Different is good" once, so Kerem wants all things in his life to be different. Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants allsubstrings 

Codeforces Round #352 (Div. 2) A Summer Camp

Every year, hundreds of people come to summer camps, they learn new algorithms and solve hard problems. This is your first year at summer camp, and you are asked to solve the following problem. All integers starting with 1 are written in one line. Th

Codeforces Round #352 (Div. 2) ABCD

Problems # Name     A Summer Camp standard input/output 1 s, 256 MB    x3197 B Different is Good standard input/output 2 s, 256 MB    x2870 C Recycling Bottles standard input/output 2 s, 256 MB    x664 D Robin Hood standard input/output 1 s, 256 MB  

Codeforces Round #352 (Div. 2) C. Recycling Bottles 贪心

C. Recycling Bottles It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin. We can think Central Perk as coordinate plane. There are n bottle

Codeforces Round #279 (Div. 2) ABCD

Codeforces Round #279 (Div. 2) 做得我都变绿了! Problems # Name     A Team Olympiad standard input/output 1 s, 256 MB  x2377 B Queue standard input/output 2 s, 256 MB  x1250 C Hacking Cypher standard input/output 1 s, 256 MB  x740 D Chocolate standard input/

Codeforces Round #428 (Div. 2)

Codeforces Round #428 (Div. 2) A    看懂题目意思就知道做了 #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i