【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2

T1

一直没有详细看过位运算的我瑟瑟发抖。出题人给了帮助（有用但是不多）。直接讲考试想法：
首先，手玩样例后，果断猜测：将两个数转化为二进制之后，把头对齐，然后找出不同位，再加上二者位数之差。结果：\(0Pts\)
之后，又想了很久，发现了 按位与等价于将原来二进制数中的1变为0，按位或等价于将原来二进制数中的0变为1。但是，当时脑子抽了，又认为按位与可以实现0变1，按位或可以实现添位。前者错误，后者没必要。这样一来，结果：\(0Pts\)。
终于，又过了很久，才发现自己的问题。得出正解：将两个二进制数尾部对齐，然后对于短的，前面补齐0，使二者等长。然后一位一位判断，0变1和1变0各自只需要1次操作就能全部实现，所以只需统计这种情况出现没。结果：\(100Pts\).

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=10000+5, INF=0x3f3f3f3f;
ll T,n,m; 
string To2(ll n){
	string s,l;
	ll ts=n;
	while(ts!=0){
		if(ts%2==0){
			s+='0';
		}
		else{
			s+='1';
		}
		ts/=2;
	}
	return s;
}//转二进制
int main() {
	cin>>T;
	while(T--){
		scanf("%lld%lld",&n,&m);
		string k1=To2(n),k2=To2(m);
		
		int s1=k1.size(),s2=k2.size(),ans=0;
		if(s1<s2)for(int i=s1;i<=s2-1;i++)k1=k1+'0';
		else if(s1>s2)for(int i=s2;i<=s1-1;i++)k2=k2+'0';//补齐
		s1=k1.size(),s2=k2.size();
		
		int a=0,b=0;//a:0->1 b:1->0
		for(int i=0;i<s1;i++){
			if(k1[i]!=k2[i]){
				if(k2[i]=='1')a=1;
				else b=1;
			}
		}
		printf("%d\n",a+b);
	}
	return 0;
}

用时：1.92h

T2

题目不难理解，但是我们可以注意到，其实矩阵的各个数字位置在哪都是一样的，都可以通过移动使得每一列上的数字一样（注意不是矩阵每个数都相同），但是这样已经足够了。又要使尽可能多的列的最大值大于\(v\)，那就尽可能让大的数分开。
可以对于每一次询问，都暴力搜索原矩阵，得出答案。可得\(50Pts\)。
剪枝其实也很简单（但是本蒟蒻最后时刻才发现），当找到的大于\(v\)的数已经比\(n\)多后，后面的就不用再搜索了。得分：\(100Pts\)。
(试图用vector直接过的屑)

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=1000+5, INF=0x3f3f3f3f;
ll n,q;
ll x;
ll v;
vector<ll>V;
int main(){
	scanf("%lld%lld",&n,&q);
	for(re ll i=1;i<=n;i++)
		for(re ll j=1;j<=n;j++){
			scanf("%lld",&x);
			V.push_back(x);
		}
	sort(V.rbegin(),V.rend());
	/*for(int i=0;i<V.size();i++)cout<<V[i]<<' ';*/
	
	for(re ll i=1;i<=q;i++){
		scanf("%lld",&v);
		ll ans=n;
		for(re ll j=0;j<V.size();j++){
			if(V[j]<v||j>n){
				ans=j;
				break;
			}
		}
		if(ans>=n)ans=n;
		printf("%lld\n",ans);
	}
	return 0;
}

用时：3.9h

T3

嘎嘎不会，嘎嘎骗分，看到熟悉的菊花图和链表，直接选一个嘎嘎做（菊花在前，菊花有限)(doge)

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=1000000+5, INF=0x3f3f3f3f;
int n;
vector<int> G[N];
int a[N];
//Jvhua
int ru[N];
int main(){
	cin>>n;
	
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		ru[x]++;ru[y]++;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	if(ru[1]==n-1){
		cout<<-1<<endl;
	}else{
		if(n%2==0)cout<<-1<<endl;
		else{
			int v=G[1][0],t=0;
			for(int i=1;i<=n;i++){
				if(i==1||i==v)cout<<0<<' ';
				else if(t<(n-2)/2){
					t++;cout<<0<<' ';
				}
				else cout<<1<<' ';
			}
		}
	}
	return 0;
}

用时：3.6h

期望得分：IOI赛制什么期望得分（
实际得分：205Pts
rk：867
传送门