【USACO1.3】解题报告

前言

这一章主要考察的是一些简单的数论和思维转化能力。还是相对来说比较简单的。
USACO:http://train.usaco.org

1.3.2.Milking Cows

思路：

前缀和基础题。
每次读到有人在 $l$ 到 $r$ 的时间段内工作，就将 $a[l]++,a[r]--$ ，之后用前缀和，如果 $a[x]>0$ ，说明在 $x$ 的时候有人挤奶，否则没有。
时间复杂度 $O(t)$ （ $t$ 表示时间）
另外，暴力时间复杂度 $O(tn)$ ，线段树时间复杂度 $O(tlogt)$

代码：

/*
ID:ssl_zyc2
TASK:milk2
LANG:C++
*/

#include <cstdio>
#include <iostream>
#define N 1000100
using namespace std;

int a[N],n,x,y,max1,max2,k1,k2,s,t;

int main()
{
	freopen("milk2.in","r",stdin);
	freopen("milk2.out","w",stdout);
	scanf("%d",&n);
	s=1e9;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if (t<y) t=y;
		if (s>x) s=x;  //取时间
		a[x]++;
		a[y]--;
	}
	for (int i=s;i<=t;i++)
	{
		a[i]+=a[i-1];  //前缀和
	 	if (a[i])
	 	{
	 		if (k2+1>max2) max2=k2;
	 		k2=0;
	 		k1++;
	 	}
	 	else
	 	{
	 		if (k1-1>max1) max1=k1;
	 		k1=0;
	 		k2++;
	 	}
	}
	printf("%d %d\n",max1,max2);
	return 0;
}

1.3.3.Transformations

思路：

模拟啊。。。

转 $90°=a[i][j]$ 转换到 $a[j][n-i+1]$
转 $180°=a[i][j]$ 转换到 $a[n-i+1][n-j+1]$
转 $270°=$ 逆时针转 $90°$
反射 $=swap(a[i],a[n-i+1])$
反射 $+90°/180°/270°$ = $4+1/2/3$
不变 $=$ 废话
无法成立 $=!1\ \&\&\ !2\ \&\&\ !3\ \&\&\ !4\ \&\&\ !5\ \&\&\ !6$

代码：

/*
ID:ssl_zyc2
TASK:transform
LANG:C++
*/

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 20
using namespace std;

char a[N][N],b[N][N];
int n;

bool check1()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (a[i][j]!=b[j][n-i+1]) return 0;
	return 1;
}

bool check2()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (a[i][j]!=b[n-i+1][n-j+1]) return 0;
	return 1;
}

bool check3()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (a[j][n-i+1]!=b[i][j]) return 0;
	return 1;
}

bool check4()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (a[i][j]!=b[i][n-j+1]) return 0;
	return 1;
}

bool check5()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n/2;j++)
	  swap(a[i][j],a[i][n-j+1]);
	bool ok=false;
	if (check1()) ok=1;
	if (check2()) ok=1;
	if (check3()) ok=1;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n/2;j++)
	  swap(a[i][j],a[i][n-j+1]);
	return ok;
}

bool check6()
{
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (a[i][j]!=b[i][j]) return 0;
	return 1;
}

int main()
{
	freopen("transform.in","r",stdin);
	freopen("transform.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++) 
	 cin>>a[i]+1;
	for (int i=1;i<=n;i++)
	 cin>>b[i]+1;
	if (check1()) cout<<1;
	else if (check2()) cout<<2;
	else if (check3()) cout<<3;
	else if (check4()) cout<<4;
	else if (check5()) cout<<5;`
	else if (check6()) cout<<6;
	else cout<<7;
	printf("\n");
	return 0;
	
}

1.3.4.Name That Number

思路：

这道题题目看懂了就很简单。
把 $dict.txt$ 里面的字符串全部转化成数字，与读入的 $n$ 看看是否一样，一样的额话就输出。
要用 $long\ long$

代码：

/*
ID:ssl_zyc2
TASK:namenum
LANG:C++
*/

#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#define MAXN 1001000
#define ll long long
using namespace std;

string s;
ll n;
bool ok;

ll change(string s)
{
	ll ss=0;
	for (int i=0;i<s.size();i++)
	 if (s[i]>='A'&&s[i]<='C') ss=ss*10+2;  //依次判断
	 else if (s[i]>='D'&&s[i]<='F') ss=ss*10+3;
	 else if (s[i]>='G'&&s[i]<='I') ss=ss*10+4;
	 else if (s[i]>='J'&&s[i]<='L') ss=ss*10+5;
	 else if (s[i]>='M'&&s[i]<='O') ss=ss*10+6;
	 else if (s[i]>='P'&&s[i]<='S') ss=ss*10+7;
	 else if (s[i]>='T'&&s[i]<='V') ss=ss*10+8;
	 else if (s[i]>='W'&&s[i]<='Z') ss=ss*10+9;
	return ss;
}

int main()
{
	freopen("namenum.in","r",stdin);
	freopen("namenum.out","w",stdout);
	cin>>n;
	freopen("dict.txt","r",stdin);
	while (cin>>s) 
	 if (change(s)==n)   //相等
	  cout<<s<<endl,ok=true;
	if (!ok) printf("NONE\n");
	return 0;
}

1.3.5.Palindromic Squares

思路：

枚举 $i=1\ to\ 300$ ，判断 $i^2$ 是不是 $n$ 进制下的回文串。
模拟+数论，数学。

代码：

/*
ID:ssl_zyc2
TASK:palsquare
LANG:C++
*/

#include <cstdio>
#define N 25
using namespace std;

const char d[]={'0','1','2','3','4','5','6','7','8','9',
				'A','B','C','D','E','F','G','H','I','J'};  //打好1~20的表
int n,m,a[N];

void change(int x)  //转换进制
{
	while (x)
	{
		a[++m]=x%n;
		x/=n;
	}
}

bool check()
{
	for (int i=1;i<=m/2;i++)  //判断是否回文
	 if (a[i]!=a[m-i+1]) return 0;
	return 1;
}

void dfs(int x)  //输出i^2的n进制形式
{
	if (!x) return;
	dfs(x/n);
	putchar(d[x%n]);
}

int main()
{
	freopen("palsquare.in","r",stdin);
	freopen("palsquare.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=300;i++)
	{
		m=0;
		change(i*i);
		if (check())
		{
			dfs(i);
			printf(" ");
			for (int i=m;i>=1;i--) 
			 putchar(d[a[i]]);
			printf("\n");
		}
	}
	return 0;
}

1.3.6.Dual Palindromes

思路：

简单的模拟。
从 $m$ 开始往后枚举，每个数判断一下就好了。

代码：

/*
ID:ssl_zyc2
TASK:dualpal
LANG:C++
*/

#include <cstdio>
#include <cstring>
#define N 25
using namespace std;

int n,m,a[N],k;

bool check(int x,int y)
{
	int t=0;
	memset(a,0,sizeof(a));
	while (x)  //转换进制
	{
		a[++t]=x%y;
		x/=y;
	}
	for (int i=1;i<=t/2;i++)  //判断回文
	 if (a[i]!=a[t-i+1]) return 0;
	return 1;
}

int main()
{
	freopen("dualpal.in","r",stdin);
	freopen("dualpal.out","w",stdout);
	scanf("%d%d",&n,&m);
	while (n)
	{
		m++;
		k=0;
		for (int i=2;i<=10;i++)
		 if (check(m,i)) k++;
		if (k>1)  //符合题意
		{
			printf("%d\n",m);
			n--;
		}
	}
	return 0;
}