题目描述
我们称一个矩阵是下降矩阵，当且仅当，矩阵的每一列都是严格下降的。很显然，这个要求很苛刻，大多数矩阵都无法满足。但是显然如果消去一些行，一定可以使得这个矩阵变成下降矩阵。
现在给出一个n行m列的矩阵，请你求出最少消去多少行，可以使得这个矩阵变为下降矩阵。
输入
输入第一行包含两个正整数n,m分别表示矩阵的行数和列数。(1<=n,m<=300)
接下来n行，每行有m个数,中间用空格隔开，每个数都小于2^31.
接下来n行，每行有m个数,中间用空格隔开，每个数都小于2^31.
输出
输出仅包含一个整数，即最少消去的行数。
样例输入 Copy
1 3
1 2 3
样例输出 Copy
0
把每一行元素看作一个向量，或者说一个"行元素"。题目要求的就是对于N个向量来说的最长的严格下降子序列长度，然后用N减去这个严格下降子序列长度就是答案了。方法与求LIS类似。
#include<bits/stdc++.h>
using namespace std; int N,M;
int v[][];
int f[]={};
bool cmp(int di,int dj){
for(int i=;i<=M;++i){
if(v[di][i] <= v[dj][i] ) return ;
}return ;
}
int main()
{
cin>>N>>M;
for(int i=;i<=N;++i)
for(int j=;j<=M;++j)
cin>>v[i][j];
f[]=;
int ans=;
for(int i=;i<=N;++i){
f[i]=;
for(int j=;j<i;++j){
if(cmp(j,i)){
f[i]=max(f[i],f[j]+);
}
}
ans=max(ans,f[i]);
}
cout<<N-ans<<endl;
return ;
}
题目描述
一天，Chika 对大小接近的点对产生了兴趣，她想搞明白这个问题的树上版本，你能帮助她吗？Chika 会给 你一棵有根树，这棵树有 n 个结点，被编号为 1 n，1 号结点是根。每个点有一个权值，i 号结点的权值为 a[i]。如果 u 是 v 的祖先结点，并且 abs(a[u]−a[v]) ≤K，那么 (u,v) 被称作一个“** 大小接近的点对 **”。 对于树上的每个结点 i，你都需要计算以其为根的子树中的“大小接近的点对”的数量。你需要知道：
(1) abs(x) 代表 x 的绝对值。
(2) 每个结点都是其自身的祖先结点.
(1) abs(x) 代表 x 的绝对值。
(2) 每个结点都是其自身的祖先结点.
输入
输入文件的第一行包含两个整数 n (1≤n≤105) 和 k (1≤k≤109)，代表树中结点总数, 以及“大小接近的点对”的大小之差的上界。
第二行包含 n 个整数，第 i 个整数是 a[i] (1≤ a[i] ≤109)，代表 i 号结点的权值。
第三行包含 n−1 个整数，第 i 个整数是 i+1 号结点的父结点。
第二行包含 n 个整数，第 i 个整数是 a[i] (1≤ a[i] ≤109)，代表 i 号结点的权值。
第三行包含 n−1 个整数，第 i 个整数是 i+1 号结点的父结点。
输出
输出应该包含n行，每一行包括一个整数。第i行的整数代表以i为根的子树中的“大小接近的点对”的数量。
样例输入 Copy
7 5
2 4 4 1 4 6 4
1 2 3 1 2 3
样例输出 Copy
19
11
5
1
1
1
1
比赛的时候推出来是主席树了，奈何很久没写忘记关键步骤了= =
先跑dfs先序对节点重新编号，然后按照新编号依次update，问题就转化为求在[L,R]编号区间内的满足a[u]-K<=x<=a[u]+K的x的数目。
注意答案会爆int，很操蛋。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((L+R)>>1)
const int maxn=;
int N,K;
LL ans[maxn];
int a[maxn],idx[maxn],_idx[maxn],cur=,sons[maxn];
vector<int>g[maxn];
int root[maxn];
int tot=,ch[maxn*][];
int sum[maxn*]; void update(int pre,int &now,int L,int R,int val){
tot++;
ch[tot][]=ch[pre][],ch[tot][]=ch[pre][];
sum[tot]=sum[pre]+,now=tot;
//cout<<"now="<<now<<" "<<pre<<endl;
if(L==R){
return;
}
if(val<=mid){
update(ch[pre][],ch[now][],L,mid,val);
}
else{
update(ch[pre][],ch[now][],mid+,R,val);
}
}
int ask(int pre,int now,int L,int R,int l,int r){
if(L>=l && R<=r){
return sum[now]-sum[pre];
}
int res=;
if(r<=mid) res=ask(ch[pre][],ch[now][],L,mid,l,r);
else if(l>mid) res=ask(ch[pre][],ch[now][],mid+,R,l,r);
else{
res=ask(ch[pre][],ch[now][],L,mid,l,r)+ask(ch[pre][],ch[now][],mid+,R,l,r);;
}
return res;
}
/*void show(int id,int L,int R){
cout<<L<<' '<<R<<' '<<sum[id]<<endl;
if(L==R)return;
if(ch[id][0])show(ch[id][0],L,mid);
if(ch[id][1])show(ch[id][1],mid+1,R);
}*/
void dfs(int u){
idx[u]=++cur;
_idx[cur]=u;
sons[u]=;
for(auto v:g[u])dfs(v),sons[u]+=sons[v];
}
void solve(int u){
ans[u]=ask(root[idx[u]-],root[idx[u]-+sons[u]],,,max(,a[u]-K),min(,a[u]+K));
for(auto v:g[u]){
solve(v);
ans[u]+=ans[v];
}
}
int main(){
cin>>N>>K;
for(int i=;i<=N;++i)scanf("%d",a+i);
for(int i=,fa;i<=N;++i){
scanf("%d",&fa);
g[fa].push_back(i);
}
dfs();
for(int i=;i<=N;++i){
update(root[i-],root[i],,,a[_idx[i]]);
}
solve();
for(int i=;i<=N;++i)printf("%lld\n",ans[i]); return ;
}
题目描述
咕咕最近在学习初等数论，并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数，自变量为 一个实数，因变量为一个整数，这个整数恰好是小于或等于自变量的最大的整数，通常记做 ⌊x⌋。例如， ⌊2.5⌋ = 2,⌊2⌋ = 2,⌊−2.5⌋ = −3。
咕咕发现，给定一个 a，并不是所有的自然数 n 都存在一个正整数 i 使得 ⌊n/i⌋ = a。那么，如果给定 l,r，咕咕好奇在区间 [l,r] 中有多少个正整数能使这个等式有正整数解 i 呢？
那么，聪明的你，你能告诉咕咕吗？
咕咕发现，给定一个 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。
当 n = 39,a = 7 时，能找到 i = 5 使得 ⌊39 /5 ⌋ = 7。
规律题，找规律or打表可以发现，这些满足条件的数字可以按照k*a分类，
1,2......a......2a,2a+1......3a,3a+1,3a+2............a*a,....a*a+a-1......（a+1)*a......k*a......
规律很容易发现，就是找不同的正整数k,那么从k*a开始往后的k个数字(包括k*a)只要在区间里面都是满足条件的，k等于多少就有多少个满足条件的数字，但注意当k>a的时候最多也只有a个数字而不是k个数字了。
利用容斥思想，找出[1,r]内的个数和[1,l-1]的个数做差就是答案。
code:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL T,a,l,r;
LL solve(LL n){
if(n<) return ;
LL ans=;
LL div=n/a,rem=n%a;
if(div<=a){
ans+= div*(div-)/;
if(div*a+div-<=n){
ans+=div;
}
else{
ans+=(n-div*a+);
}
}
else{
ans+=(+a)*a/;
ans+=(div-a-)*a;
if(div*a+a-<=n){
ans+=a;
}
else{
ans+=(n-div*a+);
}
}
return ans;
}
int main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&a,&l,&r);
printf("%lld\n",solve(r)-solve(l-));
}
return ;
}
问题 I: Childhood dream
时间限制: 1 Sec 内存限制: 256 MB
提交: 63 解决: 18
[提交] [状态] [讨论版] [命题人:zhd]
题目描述
你童年时期就有一个梦想，想要加入 ACM(Association of Calculation and Magic)，今天，这个机会终于 来了。
但是 ACM 只想要哪些天赋异禀的人, 比如像 tourist，他们给了你一道题来检测你是否足够机智。
猜一个长度为 m 数字串，总共有 n 个提示串，解释如下：
8640 0A2B
A 前面的数字说明与答案相比，有多少个位置上的数字是相同的。 B 前面的数字说明与答案相比，有多 少个数字是相同的，但是位置不一样。
0 A 就表示给出的串没有任何位置和答案是相同的。 2 B 就表示给出的串中有两个数字和答案相同，但 是位置不一样。
所以，对于上面那个提示串 6457 是一个合理的答案，但是 1234 并不是。
现在给你 N(N<=100) 个提示串（如上所示），你需要去找到一个数字串来符合每一个提示串的要求。
提示串中的每个数字都是不同的，即一个串中不会存在相同的数字。
你能解决这个问题并加入 ACM 吗？
但是 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
然后是 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 暴力搜索，由于不可行的情况很多，减枝会减去很多方案，所以直接搜完事。
#include<bits/stdc++.h>
using namespace std; char str[][];
int A[],B[],tot[][];
int N,M;
int c[];
bool ok=;
bool check(int n,int type){
for(int i=;i<=N;++i){
int _A=,_B=;
for(int j=;j<n-;++j){
if(str[i][j]-'' == c[j+]){
_A++;
}
else{
if(tot[i][c[j+]]){
_B++;
}
}
}
if(type== &&(_A>A[i] || _B>B[i] )) return ;
if(type== &&(_A!=A[i] || _B!=B[i])) return ;
}
return ;
}
void dfs(int u){
if(ok)return;
if(!check(u,)){
return;
}
if(u==M+){
if(check(M+,)){
ok=;
for(int i=;i<=M;++i)cout<<c[i];cout<<endl;
}
return;
}
else{
for(int i=;i<;++i){
c[u]=i;
dfs(u+);
}
}
}
int main()
{
cin>>N>>M;
for(int i=;i<=N;++i){
cin>>str[i]>>A[i]>>B[i];
}
for(int i=;i<=N;++i){
for(int j=;j<M;++j){
tot[i][str[i][j]-'']++;
}
}
dfs();
return ;
}