Codeforces Round #378 (Div. 2) Analyses

Return posted @ Nov 08, 2016 05:01:18 AM in OI with tags #378 733 Div 2 codeforces , 767 阅读

懒癌晚期,没的救了xD

A.Grasshopper And the String

Problems:一只蚂蚱从左跳到右,每次只能跳{A,E,I,O,U,Y},问两次跳之间的距离的最大值

Analysis:简单模拟即可

Tags:Implementation

B.Parade

Problems:给你n排士兵及每排士兵的左、右脚分别伸出的数目,可以交换其中一排的左右脚伸出数,问max{|L-R|}

Analysis:鉴于只有10^5,那么暴力交换就可以了

Tags:Implementation

C.Epidemic in Monstropolis

Problems:给你一个序列和另一个序列,对于后者可以进行merge操作,条件为merge的前者大于后者(R)或后者大于前者(L),问是否可以使后者变成前者,并输出方案

Analysis:首先我们知道后面那个序列要是可能变成前者,那么最后构造出来的数肯定是一一对应的,所以可以从前向后构造,如果不能,则输出否即可,那么考虑构造,对于当前目的序列的x,在原序列若找到一段序列和为x,即视为构造成功,之后方案构造只需向右merge后向左merge再向右merge即可,具体可以看代码实现

Tags:Implementation, Two pointers

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 1010
#define Maxe 100010
typedef long long ll;

struct Data
{
	int m;
	char s;
}Ans[Maxe];
int n, a[Maxn], b[Maxn], k, Cnt;

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline void Go_die() { puts("NO"); exit(0); }

int main()
{
    read(n);
    for (int i=1; i<=n; i++) read(a[i]);
    read(k);
    for (int i=1; i<=k; i++) read(b[i]);
    int id=1, last=1;
    for (int i=1; i<=k; i++)
    {
        int Max=0, pos=0, _pos=0, Sig=0;
        for (; (id<=n) && (Sig<b[i]); id++)
        {
            Sig+=a[id];
            if (Sig>b[i]) Go_die();
            if (a[id]>Max) Max=a[id], pos=id;
        }
        if (Sig!=b[i]) Go_die();
        if ((pos==last) && (a[pos+1]==Max)) while (a[pos+1]==Max) pos++;
        _pos=pos+1; int Res=i+pos-last;
        while ((_pos<id) && (a[_pos]<Max))
        {
            Max+=a[_pos++];
            Ans[++Cnt].m=Res; Ans[Cnt].s='R';
        }
        int __pos=pos-1;
        while ((__pos>=last) && (a[__pos]<Max))
        {
            Max+=a[__pos--];
            Ans[++Cnt].m=Res--; Ans[Cnt].s='L';
        }
        while ((_pos<id) && (a[_pos]<Max))
        {
            Max+=a[_pos++];
            Ans[++Cnt].m=Res; Ans[Cnt].s='R';
        }
        if (Max!=b[i]) Go_die();
        last=id;
    }
    if (last!=n+1) Go_die(); 
    puts("YES");
    for (int i=1; i<=Cnt; i++) printf("%d %c\n", Ans[i].m, Ans[i].s);
}

D.Kostya the Sculptor

Problems:给你n个长方形,最多选取两个长方形,问能切割出来的最大的球半径的方案

Analysis:这题反倒是比C题好写了,首先对于每个长方形,我们将边长排序,最大半径显然等于最短边的边长,之后考虑合并,合并肯定是有一个面一样然后让另一条边增长为优,所以只需维护面就可以了,需要用到map(或者离散化???)

Tags:Greedy, Data Structure

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
typedef long long ll;

map<pair<int, int> , pair<int, int > > Srh;

int n, a, b, c, Min, Mid, Max, Line_max, Merge, Id;
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

int main()
{
	read(n);
	for (int i=1; i<=n; i++)
	{
		read(a), read(b), read(c);
		Max=max({a, b, c}), Min=min({a, b, c}), Mid=a+b+c-Max-Min;
		if (Min>Line_max) Line_max=Min, Id=i, Merge=-1;
		if (Srh[{Mid, Max}].first)
		{
			Min=min({Mid, Max, Min+Srh[{Mid, Max}].first});
			if (Min>Line_max)
			{
				Line_max=Min;
				Id=i;
				Merge=Srh[{Mid, Max}].second;
			}
		}
		Min=min({a, b, c});
		Srh[{Min, Mid}]=max(Srh[{Min, Mid}], {Max, i});
		Srh[{Min, Max}]=max(Srh[{Min, Max}], {Mid, i});
		Srh[{Mid, Max}]=max(Srh[{Mid, Max}], {Min, i});
	}
	if (Merge==-1) { puts("1"); printf("%d\n", Id); }
	else { puts("2"); printf("%d %d\n", Id, Merge); }
}
PSPCL Bill History 说:
Aug 07, 2022 08:06:23 PM

The Government of Punjab in coordination with their State electricity department created the PSPCL organization. It is a Punjab state power corporation limited. It is solely responsible for management and supply of power across the state. Through this Government has unified the supply chain of power to provide uninterrupted electricity services to consumers. PSPCL Bill History At the same time has created a portal for citizens to pay for all their PSPCL electricity bills online. If you’ve recently paid your electricity bill for Punjab through the PSPCL portal or if it for few years. Then you can follow this process that will help you understand how you can get your PSPCL bill history for every year bill payments.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter