团队练习记录10.9

题目链接：https://qoj.ac/contest/1480
这次有个强队去讲课，偶幸校队赛时第一

C - Catch You Catch Me

队友写的，签到题吧？

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
const ll N=1e6+5;
const ll mod=1e9+7;

ll t,n,m;
vector<ll> G[N];
ll val[N];

void fio(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void dfs(int u,int fa){
	for(auto i:G[u]){
		if(i==fa) continue;
		dfs(i,u);
		val[u]=max(val[i]+1,val[u]);
	}
	if(G[u].size()==1 && u!=1) val[u]=1;
	return;
}

signed main()
{
	fio();
	ll u,v;
	cin >> n;
    for(int i=1; i<n; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	ll ans=0;
//	for(int i=1; i<=5; i++){
//		cout << val[i] << endl;
//	}
	for(auto i:G[1]){
		ans+=val[i];
	}
	cout << ans << endl;
	return 0;
}

G - Let Them Eat Cake

暴力枚举，递归or数组暴力

//维护4个log点
#include<iostream>
#include<string.h>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
void fio()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
ll a[250000];
ll b[250000];
ll c[250000];
int main()
{
	fio();
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	ll ans=0;
	if(n==1)
	{
		cout<<0<<endl;
		return 0;
	}
	ll l=n;
	while(1)
	{
		ans++;
		ll r=0;
		ll cnt=0;
		for(ll i=1;i<=l;i++)
		{
			if(b[i]==1)
			{
				b[i]=0;
			}
			else
			{
				r++;
				c[r]=a[i];
			}
			//b[i]=0;
		}
		for(ll i=1;i<=r;i++)
		{
				if(i==1&&c[i]<c[i+1])
				{
					b[i]=1;
					cnt++;
				}
				else if(i==r)
				{
					if(c[i]<c[i-1])
					{
						b[i]=1;
						cnt++;
					}
				}
				else
				{
					if(c[i]<c[i+1]||c[i]<c[i-1])
					{
						b[i]=1;
						cnt++;
					}
				}
		}
		if(r-cnt<=1)
		break;
		for(ll i=1;i<=r;i++)
		{
			a[i]=c[i];
		}
		l=r;
	}
	cout<<ans<<endl;
}

H - Life is Hard and Undecidable, but...

思维题，考虑对角线即可

//维护4个log点
#include<iostream>
#include<string.h>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
void fio()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
int main()
{
	fio();
	ll n;
	cin >> n;
	cout << n * 2 << endl;
	for (ll i = 1; i <= n*2; i++)
	{
		cout << i << " " << i << endl;
	}
}

M - Rock-Paper-Scissors Pyramid

stack堆栈维护，输者要作为强者的保护层

//维护4个log点
#include<iostream>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
void fio()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
ll ck(char x, char y)
{
	if (x == 'S')
	{
		if (y == 'P')
			return 1;
		else if (y == 'S')
			return 0;
		else
			return -1;
	}
	else if (x == 'P')
	{
		if (y == 'R')
			return 1;
		else if (y == 'P')
			return 0;
		else
			return -1;
	}
	else
	{
		if (y == 'S')
			return 1;
		else if (y == 'R')
			return 0;
		else
			return -1;
	}
}
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		stack<char>q;
		string f;
		cin >> f;
		for (ll i = f.size()-1; i >= 0; i--)
		{
			if (q.empty())
			{
				q.push(f[i]);
			}
			else
			{
				while (!q.empty())
				{
					char k = q.top();
					if (ck(f[i], k) == 1)
					{
						q.pop();
					}
					else
					break;
				}
				q.push(f[i]);
			}
		}
		char op;
		while (!q.empty())
		{
			op = q.top();
			q.pop();
		}
		cout << op << endl;
	}
}