return's Blog

懒癌晚期，没的救了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); }
}