榜单：http://acm.zzuli.edu.cn/contestrank.php?cid=1383

总结：这次参加比赛失误不断，首先是签到题连续wa，之后被A题卡到死，当时想到最长上升子序列dp了，但是一看是二维的就没有继续想下去，想着会是模拟或者贪心过，最后也没有写出来。队友开了F题，规律找出来了，但是左右边界的细节没注意，一直没有出来正解。总是，还是做题太少，这种题没有思路。

补题开启：

问题 A: 最大下降矩阵

时间限制: 1 Sec  内存限制: 512 MB
提交: 742  解决: 202
[提交] [状态] [讨论版] [命题人:外部导入]

题目描述

我们称一个矩阵是下降矩阵，当且仅当，矩阵的每一列都是严格下降的。很显然，这个要求很苛刻，大多数矩阵都无法满足。但是显然如果消去一些行，一定可以使得这个矩阵变成下降矩阵。

现在给出一个n行m列的矩阵，请你求出最少消去多少行，可以使得这个矩阵变为下降矩阵。

输入

输入第一行包含两个正整数n,m分别表示矩阵的行数和列数。(1<=n,m<=300)
接下来n行，每行有m个数,中间用空格隔开，每个数都小于2^31.

输出

输出仅包含一个整数，即最少消去的行数。

样例输入 Copy

1 3
1 2 3

样例输出 Copy

0

提示

样例二 
输入 
3 1 
3 
1 
2 
输出 
1 
 

题解：一行看作一个数，直接最长上升子序列。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int a[maxn][maxn];
int dp[maxn];

int main()
{
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)//hang
	{
		for(int j=1;j<=m;j++)//lie
		{
			cin>>a[i][j];
		}
	}
	
	for(int i=n;i>=1;i--)//hang
	{
		dp[i]=1;
		for(int k=n;k>i-1;k--)
		{
			int temp=0;
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]>a[k][j])
					temp++;
			}
			if(temp==m)
			{
				dp[i]=max(dp[i],dp[k]+1);
			}
			ans=max(ans,dp[i]);	
		}
	}
	cout<<n-ans<<endl;
	return 0;
}

问题 F: 咕咕的计数题 II

时间限制: 1 Sec  内存限制: 64 MB
提交: 1439  解决: 145
[提交] [状态] [讨论版] [命题人:外部导入]

题目描述

咕咕最近在学习初等数论，并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数，自变量为 一个实数，因变量为一个整数，这个整数恰好是小于或等于自变量的最大的整数，通常记做 ⌊x⌋。例如， ⌊2.5⌋ = 2,⌊2⌋ = 2,⌊−2.5⌋ = −3。 
 咕咕发现，给定一个 a，并不是所有的自然数 n 都存在一个正整数 i 使得 ⌊n/i⌋ = a。那么，如果给定 l,r，咕咕好奇在区间 [l,r] 中有多少个正整数能使这个等式有正整数解 i 呢？ 
 那么，聪明的你，你能告诉咕咕吗？  

输入

第一行有一个整数 T(1 ≤ T ≤ 106)，表示数据组数。接下来有 T 行，每行有三个数 a,l,r(1 ≤ a ≤ 1018,1 ≤ l ≤ r ≤ 1018)，表示一组询问。 

输出

输出 T 行，对每组询问，输出一个整数表示答案。 

样例输入 Copy

4
5 7 10
7 39 42
1000 1000 1000
27 100 1000

样例输出 Copy

1
2
1
617

提示

数据范围 
当 n = 39,a = 7 时，能找到 i = 5 使得 ⌊39 /5 ⌋ = 7。

题解：大于a^2的数全部满足条件，只需要处理小于a^2的数。注意边界，不要出现负区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll a,l,r,temp=0;
		scanf("%lld%lld%lld",&a,&l,&r);
		ll ans=0;
		if(r/a>=a&&l/a<a)
			ans+=r-a*a,r=a*a;
		else if(l/a>=a)
		{
			printf("%lld\n",r-l+1);
			continue;
		}
		if(l/a*a+l/a<=r)
			ans+=max(l/a*a+l/a-l,0ll);
		if(r/a*a+r/a>r)
			ans+=r-max(r/a*a,l)+1,temp=1;
		if(r/a-temp>=l/a+1)
			ans+=(l/a+1+r/a-temp)*(r/a-l/a-temp)/2;
		printf("%lld\n",ans);
	}
	return 0;
}

问题 I: Childhood dream

时间限制: 1 Sec  内存限制: 256 MB
提交: 307  解决: 97
[提交] [状态] [讨论版] [命题人:外部导入]

题目描述

你童年时期就有一个梦想，想要加入 ACM(Association of Calculation and Magic)，今天，这个机会终于 来了。  
但是 ACM 只想要哪些天赋异禀的人, 比如像 tourist，他们给了你一道题来检测你是否足够机智。  
猜一个长度为 m 数字串，总共有 n 个提示串，解释如下： 
 8640 0A2B  
A 前面的数字说明与答案相比，有多少个位置上的数字是相同的。 B 前面的数字说明与答案相比，有多 少个数字是相同的，但是位置不一样。 
 0 A 就表示给出的串没有任何位置和答案是相同的。 2 B 就表示给出的串中有两个数字和答案相同，但 是位置不一样。  
所以，对于上面那个提示串 6457 是一个合理的答案，但是 1234 并不是。  
现在给你 N(N<=100) 个提示串（如上所示），你需要去找到一个数字串来符合每一个提示串的要求。 
提示串中的每个数字都是不同的，即一个串中不会存在相同的数字。  
你能解决这个问题并加入 ACM 吗？  

输入

第一行两个数字，n(n<=100) 和 m(m<=9）, 提示串的数量以及目标字符串的长度。  
然后是 n 行，每行的格式如下：  
s x y  
s 是提示串，x 是 A 前的数字，y 是 B 前的数字，等同于：  
s xAyB  

输出

一行，目标串。
数据保证答案唯一。 

样例输入 Copy

6 4
5164 3 0
5174 3 0
5194 3 0
5124 3 0
5134 3 0
5104 3 0

样例输出 Copy

5184

题解：直接用next_permutation得到全排列，判断是否满足条件。（暴搜+枝剪）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
	ll k;
	int x,y;
}c[101];
int b[10];
int d[10];
int n,m,a[10]={0,1,2,3,4,5,6,7,8,9};
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%lld%d%d",&c[i].k,&c[i].x,&c[i].y);
	do
	{
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			int cnt1=0,cnt2=0;
			memset(b,0,sizeof(b));
			memset(d,0,sizeof(d));
			ll temp=c[i].k;
			int j=1;
			while(temp)
			{
				b[m-j]=temp%10;
				j++;
				d[temp%10]++;
				temp/=10;
			}
			if(j==m)	d[0]++;
			for(int i=0;i<m;i++)
			{
				if(b[i]==a[i])	cnt1++;
				if(d[a[i]]==1&&b[i]!=a[i])	cnt2++;
			}
			if(cnt1==c[i].x&&cnt2==c[i].y)	cnt++;
			else break;
		}
		if(cnt==n)
		{
			for(int i=0;i<m;i++)
			{
				printf("%d",a[i]);
			}
			printf("\n");
			break;
		}
	}while(next_permutation(a,a+10));
	
	return 0;
}