NOIP游记

考前one day

一个很普通的早晨，在7点被我妈残忍的叫醒，登上了并无多少人的地铁，在换站的时候遇到了最好的朋友(好运气++)。

上午四节课依旧是处在朦胧态度过的，中午和一个组的同学（都是大巨）互相卖了卖弱就去吃饭了（正好卡在人最少的时候，好运气++)，下午四节课不知为何听得格外认真，以至于忘记打印学籍信息了，还好教练送到我班里来了......

二晚因为怕被嫌弃（得了很尴尬的病）不能在教室里呆着，去楼梯间艰难写完了作业，顺便幻想一下明天的noip。到家已经9点了，还要听语文网课（我语文巨烂无比），到10.30才有机会碰碰电脑。简单看了一下往年noip的题，依旧是第一个比较简单，后面3个难。不知不觉1点了，睡觉睡觉~~

考试当天（上午）

因为要考试，整个晚上都没睡好，起来的时候感觉腰酸背疼手抽筋，在地铁上度过了相当长的时间（一共十几站地，大部分时间都在下象棋）终于到达中国民航大学，跟着人群走，看到前面大哥刷脸进去，天真的我还以为找到了正确的打开方式，被大学牲嘲笑后才找到特殊通道(┬┬﹏┬┬).......和上次的南开大学一样，走了很远一段路才到考点，教练已经在等我了......

补充说明：之前初赛借笔的那兄弟错过了报名时间没报上.......让我们为他默哀一分钟ヾ(•ω•`)o

开考！首先看了看卷面，先写最简单的第一题，听着身边此起彼伏的键盘敲击声，感觉周围人都好厉害，尤其是初三的，经过深思熟虑后，也只写了个暴力（没错我就是这么菜，已经有一年没刷题了，在高一结束后就没学新东西了），打了几个样例，除了最后一个3000*3000的大数据，其余都过了，本着知足常乐的原则，果断开启第二题。

相比于第一题，第二个简直是地狱难度，首先读题+理解题意就花了我20min（一共考4.5小时），之后的时间就是在草稿纸上一顿狂写，最后发现写哪个哪个不对，心态要崩，干脆再写个暴力吧，能拿20分就是好汉。但是即使是暴力也依然很难写（因为要写一个不知道嵌套层数的嵌套循环），绞尽脑汁想了1h才写完（用的递归可以解决上面提到的那个循环），还剩1.5h......

再看看第三题，难度感觉跟第二个差不多，都属于我不会但别人会的那种o(TヘTo)，但不同的是这次连暴力解法我都没想出来，最后只能看样例特征蒙了两个点。

写完第三题还剩30min，最后一个题简单看了看是dp，但是会很复杂（毕竟人家是最后一个题嘛），果断放弃，蒙了个1，考试结束。

考试当天（下午）

考试当天是大学进校园，家长开放日，按理来说家长开放和我没啥关系，但是我妈非要拉着我一块去看（不惜用一个鳕鱼汉堡，一个双层吉士汉堡，一个小薯，一个派，一盒鸡块，一杯可乐，一个冰激凌来引诱我）无奈，只能陪她一起去。看了天大南开北理工同济等我妈认为很厉害的大学，感觉我哪个都考不上......

发成绩

t1 70分，t2 20分

结束了。。。。希望能得个省二吧(っ °Д °;)っ

下附我写的代码

第一题(dict)

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,l;
int ans[N],key[N];
string arr[N],arr1[N];

bool check(string s1,string s2)//zuoxiaoweitrue
{
	for(int i=0;i<l;i++)
	{
		if(s1[i]<s2[i])
		{
			return true;
		}
		if(s1[i]>s2[i])
		{
			return false;
		}
	}
	return false;
}
void sort_arr()
{
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<n;j++)
		{
			if(!check(arr[j],arr[j+1]))
			{
				
				string temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(arr[i]==arr1[j])
			{
				key[j]=i;//原数组的j对于新i 
				break;
			}
		}
	}
}
string find_min(string s)
{
	string s1=s;
	for(int j=0;j<l;j++)
	{
		for(int i=1;i<l-j;i++)
		{
			if(s1[i]<s1[i-1])
			{
				char temp=s1[i];
				s1[i]=s1[i-1];
				s1[i-1]=temp;
			}
		}
	}
	return s1;
}
string find_max(string s)
{
	string s1=s;
	for(int j=0;j<l;j++)
	{
		for(int i=1;i<l-j;i++)
		{
			if(s1[i]>s1[i-1])
			{
				char temp=s1[i];
				s1[i]=s1[i-1];
				s1[i-1]=temp;
			}
		}
	}
	
	return s1;
}
int main()
{
	freopen("dict.in","r",stdin);
	freopen("dict.out","w",stdout);
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		arr[i]=s;
		arr1[i]=s;
		
	}
	sort_arr();
	ans[1]=1;
	for(int i=2;i<=n;i++)
	{
		string s1=find_min(arr[i]);
		if(check(s1,arr[1]))
		{
			ans[i]=1;
		}
		else
		{
			int j=2;
			for(j;j<i;j++)
			{
				if(check(s1,arr[j]))
				{
					j--;
					break;

				}
			}
			ans[i]=1;
			for(int k=1;k<=j;k++)
			{
				if(!check(s1,find_max(arr[k])))
				{
					ans[i]=0;
					break;
				}
			}
			
		}
	}

	for(int i=1;i<=n;i++)
	{
		cout<<ans[key[i]];
	}
	//cout<<find_min("baedfa");
	return 0;
}

第二题(tribool)

#include<bits/stdc++.h>
using namespace std;
const int N=5000;
int n,m,c,t,ans=100000000;
int arr[N],arr1[N];
//
struct node{
	char op;
	int x1;
	int x2;
};
node operate[N];
void copy_arr()
{
	for(int i=1;i<=n;i++)
	{
		arr1[i]=arr[i];
	}
}
bool check_arr()
{
	for(int i=1;i<=n;i++)
	{
		if(arr[i]!=arr1[i])
		{
			return false;
		}
	}
	return true;
}
void find(int num=0,int unknown=0)
{
	num+=1;
	for(int i=-1;i<=1;i++)
	{
		arr[num]=i;
		if(num==n)
		{
			copy_arr();
			for(int j=1;j<=m;j++)
			{
				char type=operate[j].op;
				
				if(type=='-')
				{
					arr1[operate[j].x1]=-arr1[operate[j].x2];
				}
				if(type=='+')
				{
					arr1[operate[j].x1]=arr1[operate[j].x2];
				}
				if(type=='T')
				{
					
					arr1[operate[j].x1]=1;
				}
				if(type=='F')
				{
				
					arr1[operate[j].x1]=-1;
				}
				if(type=='U')
				{
					
					arr1[operate[j].x1]=0;
				}
			}
			if(check_arr())
			{
				if(i==0)
					ans=min(ans,unknown+1);
				else
					ans=min(ans,unknown);
			}
			
		}
		else
		{
			if(i==0)
			{
				find(num,unknown+1);	
			}
			else
			{
				find(num,unknown);	
			}
		}
		
	}
}

int main()
{
	freopen("tribool.in","r",stdin);
	freopen("tribool.out","w",stdout);
	cin>>c>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>n>>m;
		for(int j=1;j<=m;j++)
		{
			char type;
			cin>>type;
			operate[j].op=type;
			
			
			if(type=='-')
			{
				int x1,x2;
				cin>>x1>>x2;
				operate[j].x1=x1;
				operate[j].x2=x2;
			}
			if(type=='+')
			{
				int x1,x2;
				cin>>x1>>x2;
				operate[j].x1=x1;
				operate[j].x2=x2;
			}
			if(type=='T')
			{
				int index;
				cin>>index;
				operate[j].x1=index;
			}
			if(type=='F')
			{
				int index;
				cin>>index;
				operate[j].x1=index;
			}
			if(type=='U')
			{
				int index;
				cin>>index;
				operate[j].x1=index;
			}
		}
		find();
		cout<<ans<<endl;
		ans=100000000;
	}
	
	return 0;
}

第三题(expand)

#include<bits/stdc++.h>
using namespace std;
const int N=2000;
int c,n,m,q;
int ans[N];
int arrA[N],arrB[N],arra[N],arrb[N];
int expand_num[N];

int main()
{
	freopen("expand.in","r",stdin);
	freopen("expand.out","w",stdout);
	cin>>c>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		int num;
		cin>>num;
		arrA[i]=num;
		arra[i]=num;
	}	
	for(int i=1;i<=m;i++)
	{
		int num;
		cin>>num;
		arrB[i]=num;
		arrb[i]=num;
	}
	if(n==1&&m==1)
		{
			
			if(arrA[1]!=arrB[1])
			{
				ans[0]=1;
			}
			else
			{
				ans[0]=0;
			}
		}
	if(c==2)
		{
			if(n==2)
			{
				if(m==1)
				{
					if(((arrB[1]-arrA[1])*(arrB[1]-arrA[2]))>0)
					{
						ans[0]=1;
					}
				}
				else
				{
					if(((arrA[1]-arrB[1])*(arrA[2]-arrB[2]))>0)
					{
						ans[0]=1;
					}
				}
			}
			
		}
	for(int i=1;i<=q;i++)
	{
		int n1,n2,from,to;
		cin>>n1>>n2;
		for(int j=1;j<=n1;j++)
		{
			cin>>from>>to;
			arra[from]=to;
		}
		for(int j=1;j<=n2;j++)
		{
			cin>>from>>to;
			arrb[from]=to;
		}
		if(n==1&&m==1)
		{
			if(arra[1]!=arrb[1])
			{
				ans[i]=1;
			}
			else
			{
				ans[i]=0;
			}
			
		}
		if(c==2)
		{
			if(n==2)
			{
				if(m==1)
				{
					if(((arrb[1]-arra[1])*(arrb[1]-arra[2]))>0)
					{
						ans[i]=1;
					}
				}
				else
				{
					if(((arra[1]-arrb[1])*(arra[2]-arrb[2]))>0)
					{
						ans[i]=1;
					}
				}
			}
			
		}
	}
	cout<<ans[0];
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i];
	}

	return 0;
} 

第四题我只写了个输出，没必要发了，总之就是非常菜（￣︶￣）↗