看心情填坑

人生三大错觉：我能绝杀，我就差一点，A题可以乱来

A：

现在你有两个游戏机要充电而且只有一个充电器，每秒游戏机充电的话电量+1，否则电量-2，当两个游戏机电量都为1或者其中之一电量为0的时候游戏结束，当一个电量为1的时候只能充这个，问最多能撑几秒。

a,b≤100，直接模拟，WA7，行行行我写记忆化搜索

#include<cstdio>
#include<algorithm>
using namespace std;
int a,b,ans;
int dp[205][205];
int work(int a,int b){
	if(a==0)return 0;
	if(b==0)return 0;
	if((a==1)&&(b==1))return 0;
	if(a==1)return work(2,b-2)+1;
	if(b==1)return work(a-2,2)+1;
	if(dp[a][b])return dp[a][b];
	dp[a][b]=max(work(a-2,b+1),work(a+1,b-2))+1;
	return dp[a][b];
}
int main(){
	scanf("%d%d",&a,&b);
	printf("%d",work(a,b));
}

B

现在你有n个数要排列，使得a_i<a_i+1(1≤i＜n)尽可能多，求这个数。

可以理解每次弄出一个上升子序列，全部弄完为止，要至少弄几次。懒得想了，n≤1000直接O(n²)模拟。

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1005];
bool b[1005];
int n,p;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int ans=0;
	while(p<n){
		int k=-1;
		for(int j=1;j<=n;j++)if((!b[j])&&(a[j]>k))k=a[j],b[j]=true,ans++,p++;
		ans--;
	}
	printf("%d",ans);
}

C：

n个点，求曼哈顿距离和欧几里得距离相等的点对数量。

开场C是个明智的选择。手撸一下发现就是问x坐标相等或y坐标相等的点对数，直接容斥。

#include<cstdio>
#include<algorithm>
using namespace std;
struct point{
	int x,y;
}p[200005];
long long ans;
int n;
bool cmp1(point k1,point k2){
	if(k1.x!=k2.x)return k1.x<k2.x;
	else return k1.y<k2.y;
}
bool cmp2(point k1,point k2){
	if(k1.y!=k2.y)return k1.y<k2.y;
	else return k1.x<k2.x;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp1);
	int s=0;
	for(int i=1;i<=n;i++)if(p[i].x!=p[i-1].x){
		ans+=1LL*s*(s-1)/2;
		s=1;
	}else s++;
	ans+=1LL*s*(s-1)/2;
	s=0;
	sort(p+1,p+1+n,cmp2);
	for(int i=1;i<=n;i++)if(p[i].y!=p[i-1].y){
		ans+=1LL*s*(s-1)/2;
		s=1;
	}else s++;
	ans+=1LL*s*(s-1)/2;
	s=0;
	for(int i=1;i<=n;i++)if((p[i].y!=p[i-1].y)||(p[i].x!=p[i-1].x)){
		ans-=1LL*s*(s-1)/2;
		s=1;
	}else s++;
	ans-=1LL*s*(s-1)/2;
	printf("%I64d",ans);
}

D：

现在你有n张照片，初始在第一张的位置，你看一张标号为w的需要b+1的时间，标号为h的需要1时间，从位置K切换到K+1或者K-1需要时间a,位置1和位置n也可以a时间内切换。同一张照片可以多次切换到但是不需要花费看的时间，也不计算答案。问T时间内最多可以看几张照片。

第一眼感觉是dp，第二眼感觉枚举一边二分另一边，然后被开场D33分钟A掉的费老板婊了_(:зゝ∠)_

显然最优方案是往左走一段路然后掉头一直往右走，或者往右走一段路之后掉头一直往左走。我们就可以枚举一边二分出来另一边，每次先走右边还是先走左边选较优的一种。

但实际上这个东西是可以均摊O(1)维护的（%费老板）

顺便安利一下http://www.luogu.org/problem/show?pid=2390我还在玩泥巴的时候的脑洞并没有什么卵的人做

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,b,t,k,ans,now;
long long sum[500005];
char s[500005];
int work(char c){return c=='h'?1:b+1;}
int main(){
	scanf("%d%d%d%d",&n,&a,&b,&t);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+work(s[i]);
	int k=2;
	for(int i=1;i<=n;i++){
		while(((n-k+i+1LL*min(i-1,n-k+1))*a+sum[n]-sum[k-1]+sum[i]>t)&&(k<=n))k++;
		if(k>n)break;
		ans=max(n-k+1+i,ans);
		if(ans==n)break;
	}
	printf("%d",ans);
}

E:

你有一个n*m的矩阵需要离散，要求离散之后同一行或者同一列的两个元素大小关系不变（大于等于小于）且矩阵中最大值最小。

人生错觉之我能绝杀，最后1分40秒调出，然后CF萎了，最后30秒交上去WA2，over之后2分钟调出。

人生错觉之我就差一点，又过了2分钟费老板帮我插掉了自己。

其实就是个排序之后拓扑序，没什么意思。因为我比较傻然后就写了一个长得很丑的写法。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
struct ele{
	int x,k,ans;
}e[1000005];
int a[1000005],maxx[1000005],maxy[1000005],ans[1000005];
bool cmp(ele k1,ele k2){return k1.x<k2.x;}
bool Cmp(ele k1,ele k2){return k1.k<k2.k;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)scanf("%d",&e[i*m+j].x),e[i*m+j].k=i*m+j;
	sort(e,e+n*m,cmp);
	e[n*m].x=-1;
	for(int i=0;i<n;i++)maxx[i]=n*m;
	for(int i=0;i<m;i++)maxy[i]=n*m;
	for(int i=0;i<n*m;i++){
		e[i].ans=max(e[maxx[e[i].k/m]].ans+(e[maxx[e[i].k/m]].x<e[i].x),e[maxy[e[i].k%m]].ans+(e[maxy[e[i].k%m]].x<e[i].x));
		if(e[i].x>e[maxx[e[i].k/m]].x)maxx[e[i].k/m]=i;
		if(e[i].x>e[maxy[e[i].k%m]].x)maxy[e[i].k%m]=i;		
	}
	sort(e,e+n*m,Cmp);
	for(int i=0;i<n*m;i++){
		printf("%d ",e[i].ans);
		if((i+1)%m==0)puts("");
	}
}

后记：

1、连续5次写好保存萎掉，is-programmer会玩的

2、%div1E一血的R爷

3、%div1AKrank4的哲教

4、上紫名请辣条