A. Arena

题目大意:有(n)个人每个人有个牛逼值,当两个人打起来的时候牛逼值高的人会变的更牛逼:牛逼值(+1),如果相同则无事发生.如果有一个人牛逼值超过了所有人,那么他就是牛逼的king.问有多少个人可能会成为牛逼的king.

思路

显然只有牛逼值最小的人不能,其他人可以不停地打最小的人增加自己的牛逼值达到最大.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 105;
int a[N];

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		int minv = 105;
		forn(i,1,n)	scanf("%d",&a[i]),minv = min(minv,a[i]);
		int pres = 0;
		forn(i,1,n)	if(a[i] == minv)	++pres;
		printf("%d
",n - pres);
	}
	return 0;
}

B. Cat Cycle

题目大意:有(n)个休息点.两个猫,前者A会以(n,n-1,n-2,...1,n,n-1,n-2...)的顺序循环选择去的地点.后者B则是(1,2,3...n,1,2,3,.)的顺序.但是由于后者是个菜比,如果前者当前在(x)休息,那么后者需要往后挪一位.并且在下一刻A移动到(x+1)了之后B也不会回到(x)的位置而是继续往下走.求(k)次休息时B选择的休息地点.

数据范围:

(1 leq n,q leq 10^9)

思路

首先很容易注意到(n)是偶数的时候不会相撞,只考虑奇数下的情况.

列表可以发现:B行动的周期是(a = n / 2(↓)).那么总的循环节长度是(n*a),令(k)模之即可.接下来把问题调整到对一段循环节内的考虑:再可以注意到从第一个(n/2)的位置开始每隔(a-1)次休息会产生一次冲突,所以可以拿到一个公式:对于时刻(k)来说当前(包括此次)撞上的次数是(k/2(↓)).剩下的直接统计就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	


int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		ll n,k;scanf("%lld%lld",&n,&k);
		if(n % 2 == 0)	
		{
			ll res = k % n;
			if(res == 0)	res = n;
			printf("%lld
",res);
		}
		else
		{
			ll a = n / 2;
			ll cur = (k - 1) % (n * a);
			cur = (cur + cur / a) % n + 1;
			printf("%lld
",cur);
		}
		
	}
	return 0;
}

C. Minimum Ties

题目大意:(n)个球队,每个球队打一场,胜者加三分,输者不加分,如果平局两边各加一分.问:最少有几次平局,可以使所有球队的最终总得分相同.要求输出具体方案.

思路

不妨把比赛看成是一条边,如果是平局,由于两边都加一,可以等价于直接把这条边的影响删去.如果一定要判一个输赢,那么就相当于把一个无向边调整成有向边:有向边指向的一边表示胜利,指出的端点表示输.接着可以发现如果每个点指进来的边数都相同,就说明得分都相同.进一步考虑每个点有多少个边相关:只跟奇偶性相关.对于(n)是奇数的情况,每个点有关的边数是偶数,直接对半平分输赢就可以了.对于(n)是偶数的情况每个点有关的边数是奇数,此时必须要删除一条边(也就是平局)才能保证边数是偶数.直接构造答案就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 105;
int ans[N];

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		if(n == 2)	puts("0");
		else
		{
			if(n % 2 == 0)
			{
				forn(i,1,n / 2 - 1)	ans[i] = 1;
				ans[n / 2] = 0;
				forn(i,n / 2 + 1,n)	ans[i] = -1;
			}
			else
			{
				forn(i,1,n / 2)	ans[i] = 1;
				forn(i,n / 2 + 1,n)	ans[i] = -1;
			}
			
			forn(i,1,n)
			{
				forn(j,i + 1,n)	printf("%d ",ans[j - i]);
			}
			puts("");
		}
	}
	return 0;
}

D. Pythagorean Triples

题目大意:问三元组((a,b,c))满足(1 leq a leq b leq c leq n)且是直角三角形,满足(c=a^2-b)的个数.

数据范围:

(1 leq n leq 10^9)

思路

上来不要慌,打个表可以发现(a)一定是一个奇数,并且从(3)开始的每个奇数都有对应的解,每个(a)对应的(b,c)的大小都是单调递增的,还有(b=c-1),当然这个手推也可以.而且可以发现有大量的(n)对应的合法个数重复,进而猜想在(10^9)以内的合法三元组的个数非常少,打表之后发现也就两万个,直接塞表里查(c)在(n)的范围以内的个数就可以了.注意lower_bound在处理恰好等于的情况的时候要额外加一个.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	


int main() 
{
	vector<ll> v;
	for(ll a = 3;a <= 1e9;a += 2)
	{
		ll c = (a * a + 1) / 2;
		ll b = c - 1;
		if(c > 1e9 || b > 1e9)	break;
		v.push_back(c);
	}
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		int p = lower_bound(v.begin(),v.end(),n) - v.begin();
		if(v[p] == n)	++p;
		printf("%d
",p);	
	}
	return 0;
}

E. Cheap Dinner

题目大意:有(4)种食物,每种食物有(n_i)种,对应的价格分别是(a_i,b_i,c_i,d_i).但是由于你妈喜欢看微信公众号,得知了有(m_1)个关系表示第一种食物里的第(i)种和第二种食物里的第(j)种不能一起吃会致癌,所以你不能选择这样两个食物,其次还有(m_2)代表第二种和第三种,(m_3)表示第三种和第四种.你不光被你妈的微信公众号理论折磨得有点烦,甚至还没钱吃饭,所以你现在想知道:想要每种食物都来一份,并且这些食物之间没有触犯你妈的禁忌的前提下,最少要花多少钱.

思路

经典套路:由于微信公众号的关系只在相邻两种中触发,所以不妨把这个问题分割成三个子问题:对每个第二种食物来说,与它能在一起,且价格最低的第一种食物是谁.对第三种第四种同理求,最后答案就是合并起来.

具体来说:对于每个第二种食物来说,要知道第一种食物里不和他有匹配关系且价格最低的是多少,如果能找出来,不妨把这个(a_i)直接累加到其价格上之后参与第二轮,最后答案就是第四种的价格加上去之后的最小值.回过头来,考虑怎么求不和他有匹配关系且价格最低的选择:在一开始就把所有前一种食物的价格加入到数据结构维护,再轮到他的时候,把所有跟他有关系的删去,删完了之后看最小值,再把刚刚删掉的加回去.这样的复杂度相当于遍历所有第二种食物和所有与他有关的边,整体再乘上一个数据结构维护的复杂度,是可以过的.至于数据结构的选择就很简单了,拿一个map维护次数就可以了.

不过要注意,如果当前都没有值了,说明这个点是一个不可达点,需要特殊标记一下.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 1.5e5+7;
const ll INF = 1e18;
int n[5];
ll a[5][N];
vector<int> E[N];

inline void del(map<ll,int>& st,ll x)
{
	if(--st[x] == 0)	st.erase(x);
}

int main() 
{
	ios::sync_with_stdio(0);cin.tie(0);
	forn(i,1,4)	cin >> n[i];
	forn(i,1,4)	forn(j,1,n[i])	cin >> a[i][j];
	
	forn(cur,2,4)
	{
		int m;cin >> m;
		map<ll,int> st;
		forn(i,1,n[cur])	E[i].clear();
		forn(i,1,n[cur - 1])	
		{
			if(a[cur - 1][i] == INF)	continue;
			++st[a[cur - 1][i]];
		}
		forn(i,1,m)
		{
			int u,v;cin >> u >> v;
			if(a[cur - 1][u] == INF)	continue;
			E[v].push_back(u);
		}
		
		forn(i,1,n[cur])
		{
			for(auto& f : E[i])	del(st,a[cur - 1][f]);
			if(st.empty())	a[cur][i] = INF;
			else a[cur][i] += (*st.begin()).first;
			for(auto& f : E[i])	++st[a[cur - 1][f]];
		}		
	}
	
	ll res = 1e18;
	forn(i,1,n[4])	res = min(res,a[4][i]);
	cout << (res == INF ? -1 : res);
	
	return 0;
}