前言

本来不想来被同学硬拉着来的......

然后切了ABCD，一看E我做过类似的？然后就也A了。

可能是运气好？反正感觉上分很开心。

Signed Difficulty

题目大意

给你一个形如X.Y的数，然后如果：

• \(0\le Y\le2\)，输出X-。
• \(3\le Y\le6\)，输出X。
• \(7\le Y\le9\)，输出X+。

题解

直接if判断，然后注意一下多读入的字符'.'，直接用scanf处理掉就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	int x,y;
	scanf("%d.%d",&x,&y);
	if(0<=y&&y<=2)cout<<x<<"-";
	if(3<=y&&y<=6)cout<<x;
	if(7<=y&&y<=9)cout<<x<<"+";
    return 0;
}

Same Name

题目大意

给你\(n\)个人，每个人都有名和姓，问有没有相同的名字。

题解

两个人名字相同肯定要名和姓都相同，因为数据很小，直接两个循环枚举再判断一下就可以了。

当然肯定是可以用Hash的，为了方便的话可以用map（反正我是不会手写Hash，这辈子都不可能），注意一下名和姓中有空格，直接读入就可以了，因为我用的是string，所以读入就用getline了

具体的，如果每次读入的字符串出现过，那直接输出Yes，如果所以字符串都没有出现过，那输出No。

还有一点就是getline是会读入空格的，所以在读入\(n\)后要先getchar读掉多余的空格。

时间复杂度为\(O(n\log n)\)。

代码

#include<bits/stdc++.h>//暴力
using namespace std;
int n,m;
string a[1101],b[2002];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
			if(a[i]==a[j]&&b[i]==b[j])
			{
				cout<<"Yes";
				return 0;
			}
	}		
	cout<<"No";
	return 0;
}

#include<bits/stdc++.h>//字符串Hash
using namespace std;
string ch;
map<string,bool>f;
int main() {
	int n;
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++)
	{
		getline(cin,ch);
		if(f[ch]==true)
		{
			cout<<"Yes";
			return 0;
		}
		f[ch]=true;
	}
	cout<<"No";
    return 0;
}

Many Balls

题目大意

你有一个数\(x\)，你可以进行\(2\)类操作：

\(A.\ x=x+1\)
\(B.\ x=x* 2\)

\(x\)的初值为\(0\)，输入\(n\)，请找出一种方案使\(x=n\)。

最多只能使用\(120\)次操作。

题解

题目只规定了操作的次数范围，所以可以直接使用\(n\)次操作\(A\)。

很明显，操作\(B\)是更划算的操作，因此我应该尽可能的使用操作\(B\)，可以转化为\(n=n÷2\)，我们只要计算一下要几次才能使\(n=0\)。

但有的时候\(n\)不能整除\(2\)，这时候就要使用一次操作\(A\)，同样的可以转化为\(n=n-1\)，这样就能继续使用操作\(2\)了，这样的方法是最划算的。

具体的实现过程可以参考转二进制的代码。

当然，这样最坏的情况是\(2^k-1\)（对应二进制下每位都是\(1\)，说明每次除以\(2\)后都不能整除\(2\)，所以操作是ABAB...A），那么需要\(2k-1\)次操作，但题目说少于\(120\)次，那说明在\([1,2^{60}-1]\)内都一定有合法的解，略大于\(10^{18}\)。

注意一点是，在转二进制是我们统计答案是逆着的，所以最后要把答案倒过来，也可以用字符串处理一下。

不过题目使用的是\(SPJ\)，所以无聊的话还可以在一开始先输出几个操作\(B\)，只要满足要求就可以了，反正\(0* 2=0\)不会影响操作。

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n;
	string ans="";
	scanf("%lld",&n);
	while(n)
	{
		if(n%2==0)
		{
			ans="B"+ans;//把字符'B'加到字符串的前面
			n=n/2;
		}
		else
		{
			ans="A"+ans;//把字符'A'加到字符串的前面
			n--;
		}
	}
	cout<<ans;
    return 0;
}

Pair of Balls

题目大意

你有\(2N\)个球。每个球都有一个颜色，由\(1\)到\(N\)（包括）之间的整数表示。对于\(N\)种颜色中的每一种，正好有两个该颜色的球。

这些球装在垂直于地面放置的\(M\)个圆柱体中。最初，第\(i\)个气缸包含\(k_i\)个球，从顶部开始的第\(j\)个球颜色为\(a_{i,j}\)。

你的目标是通过重复以下操作排空所有\(M\)个气缸。

选择两个不同的非空钢瓶，并从每个钢瓶中取出最上面的钢球。在这里，拆下的两个球必须具有相同的颜色。

确定目标是否可以实现，可以输出Yes，否则输出No。

题解

我会大模拟！

考虑直接模拟，代码太丑了，不放了，好吧其实是懒得写了，可以看看别人的。

当然你如果学过一点点topsort就会发现这是个模板，首先很明显如果某一堆中$ x \(在\) y \(上面但是另一堆中\) y \(在\) x \(上面，那么就不行，因此直接把\)a_{i,1}->a_{i,j}(j\not=1)$，每两个点连一条有向边，然后跑一遍看看有没有环，有则说明不可以实现，反之可以。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
queue<int>p[N],q;
vector<int>dis[N];
int main()
{
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			int x;
			scanf("%d",&x);
			p[i].push(x);
		}
		int f=p[i].front();
		dis[f].push_back(i);
		if(dis[f].size()==2)q.push(f);
	}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		ans++;
		for(int i:dis[u])
		{
			p[i].pop();
			if(!p[i].empty())
			{
				int f=p[i].front();
				dis[f].push_back(i);
				if(dis[f].size()==2)
				q.push(f);
			}
		}
	}
	if(ans<n)puts("No");
	else puts("Yes");
	return 0;
}