- A.最大下降矩阵
- B 树上逆序对
- C 大小接近的点对
- D 文本修正
- E 咕咕的的复复读读机机
- F 咕咕的计数题 II
- G 咕咕的 01 图
- H 咕咕的搜索序列
- I Childhood dream
- J THE END IS COMING!!!!!
A.最大下降矩阵
题目：
我们称一个矩阵是下降矩阵，当且仅当，矩阵的每一列都是严格下降的。很显然，这个要求很苛刻，大多数矩阵都无法满足。但是显然如果消去一些行，一定可以使得这个矩阵变成下降矩阵。
现在给出一个n行m列的矩阵，请你求出最少消去多少行，可以使得这个矩阵变为下降矩阵。
思路：
直接按照求最长下降序列的方法来求，只是判断的时候暴力判断矩阵的一整行即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,m,a[305][305],dp[305],maxn=1;
bool check(int i,int j){
for(int k=1;k<=m;k++){
if(a[i][k]>=a[j][k]){
return false;
}
}
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
dp[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(check(i,j)){
dp[i]=max(dp[i],dp[j]+1);
}
}
maxn = max(dp[i], maxn);
}
cout<<n-maxn<<endl;
return 0;
}
B 树上逆序对
一天，Chika 在研究关于所谓的树上逆序对的问题，你能帮助她吗？她会给你一棵有根树，这棵树有 n 个 结点，被编号为 1~ n，1 号结点是根。每个点有一个权值，i 号结点的权值为 a[i]。如果 u 是 v 的祖先结点， 并且 a[u] > a[v]，那么 (u,v) 被称作一个“**逆序对 **”。
Chika 会给你 m 个任务，包含两种类型：
1 u x : 向树中添加一个新结点，其父亲为 u，权值为 x。执行完这个操作后，树的结点总数增加 1，因此该 结点的编号为 n+1（n 为添加这个点之前树中的总结点数）。
2 u : 你需要回答如果删除以 u 为根的子树，树的剩余部分的逆序对数。任意两个类型 2 的任务之间互相 独立。
你需要完成所有任务。
不会，咕咕咕
C 大小接近的点对
题目：
一天，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) 每个结点都是其自身的祖先结点.
思路：
离散化+树状数组+dfs
走到当前节点时，记录一下\([a_i-k,a_i+k]\)的点的数量，然后将自身加入树状数组，遍历子树后，再次查询\([a_i-k,a_i+k]\)的点的数量，两者做差即为子树贡献的与当前节点配对的点，将其相加后返回即可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
vector<int> alls;
vector<int> v[N];
LL a[N],s[N],n,k;
LL anss[N],c[N];
int lowbit(int x) {
return x & (-x);
}
// 单点修改
void add(int x, int y) {
for (int i = x+1; i <= alls.size(); i += lowbit(i)) c[i] += y; // 不断往父节点跳
}
// 查询Sx前缀和
LL query(int x) {
LL res = 0;
for (int i = x+1; i; i -= lowbit(i)) res += c[i]; // 不断往前一个兄弟节点跳
return res;
}
int findx(LL x){
int l=0,r=alls.size()-1;
while(l<r){
int mid=(l+r)/2;
if(alls[mid]>=x){
r=mid;
}
else{
l=mid+1;
}
}
return r+1;
}
LL dfs(int now){
anss[now] = 0; //当前节点的答案数
int l = findx(a[now] - k);
int r = findx(a[now] + k);
//cout << "l:" << query(l - 1) << "r:" << query(r) << endl;
LL sum1 = query(r) - query(l - 1);
int pos = findx(a[now]);
add(pos, 1); //把自己加入树状数组
for (int i = 0; i < v[now].size();i++){
int ne = v[now][i];
LL temp = dfs(ne);
//cout << "temp:" << temp << endl;
anss[now] += temp;
}
LL sum2 = query(r) - query(l - 1); //回溯时再查一遍
anss[now] += sum2 - sum1;
//cout << "now:" << now << "sum1：" << sum1 << "sum2:" << sum2 << "anss[now]:" << anss[now] << endl;
return anss[now];
}
int main(){
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n;i++){
scanf("%lld", &a[i]);
alls.push_back(a[i]);
alls.push_back(a[i]+k);
alls.push_back(a[i]-k);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //离散化
//cout << alls[0] << endl;
for (int i = 1; i <= n - 1;i++){
LL x;
scanf("%lld", &x);
v[x].push_back(i + 1);
}
dfs(1);
//cout << endl;
for (int i = 1; i <= n; i++)
{
printf("%lld\n", anss[i]);
}
return 0;
}
D 文本修正
签到
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
string s;
int main(){
while(cin>>s){
if(s=="henan"){
cout << "Henan" << ' ';
}
else{
cout << s << ' ';
}
}
return 0;
}
E 咕咕的的复复读读机机
签到
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,cnt[105],anss=0,maxn=0;
int main(){
cin >> n;
while(n--){
int x;
cin >> x;
cnt[x]++;
if(cnt[x]>maxn){
anss = x;
maxn = cnt[x];
}
}
cout << anss << endl;
return 0;
}
F 咕咕的计数题 II
咕咕最近在学习初等数论，并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数，自变量为 一个实数，因变量为一个整数，这个整数恰好是小于或等于自变量的最大的整数，通常记做 ⌊x⌋。例如， ⌊2.5⌋ = 2,⌊2⌋ = 2,⌊−2.5⌋ = −3。
咕咕发现，给定一个 a，并不是所有的自然数 n 都存在一个正整数 i 使得 ⌊n/i⌋ = a。那么，如果给定 l,r，咕咕好奇在区间 [l,r] 中有多少个正整数能使这个等式有正整数解 i 呢？
那么，聪明的你，你能告诉咕咕吗？
思路：
找规律，对于一个a，符合⌊n/i⌋ = a的有 $a,2a,2a+1,3a,3a+1,3*a+2..... \(等，另外还需要判断x与\)a^2$的关系，值得注意的是一定要注意先除后乘，防止爆LL
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
int t;
LL a, l, r,res;
LL solve (LL x){
if(x/a<=a){ //先除后乘，防止爆LL
long long pre = ((x / a - 1) + 1) * (x / a - 1) / 2;
if((x/a)*a+(x/a)-1<x){
return pre + (x / a);
}
else{
return pre + x - (x / a) * a + 1;
}
}
else{
return a * (a - 1) / 2 + x - a * a + 1; //这里不用担心爆LL，因为x>a*a,说明a*a小于1e18
}
}
int main(){
cin >> t;
while(t--){
scanf("%lld%lld%lld", &a, &l, &r);
res = solve(r)-solve(l-1);
printf("%lld\n", res);
}
return 0;
}
G 咕咕的 01 图
不会，咕咕咕
H 咕咕的搜索序列
题意：
给出一个dfs序，判断是否合法的dfs序的子序列
思路：
首先根据给出的dfs序设置遍历子树的优先顺序，然后再跑一遍dfs判断是否是子序列即可，至于怎么设置子树的优先顺序，直接在第一次dfs的时候由子节点更新父节点的顺序即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int t,n,m,order[N],anss[N],cnt,ep[N];
vector<int> mp[N];
void dfs(int now){
for (int i = 0; i < mp[now].size();i++){
dfs(mp[now][i]);
order[now] = min(order[now], order[mp[now][i]]);
}
}
bool cmp(int a,int b){
return order[a] <= order[b];
}
void dfs2(int now){
//cout << now << endl;
for (int i = 0; i < mp[now].size();i++){
dfs2(mp[now][i]);
}
anss[cnt++] = now;
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n;i++){
order[i] = 0x3f3f3f3f;
mp[i].clear();
}
for (int i = 2; i <= n; i++)
{
int x;
scanf("%d", &x);
mp[x].push_back(i);
}
for (int i = 1; i <= m;i++){
scanf("%d", &ep[i]);
order[ep[i]] = i;
}
dfs(1);
for (int i = 1; i <= n;i++){
sort(mp[i].begin(), mp[i].end(), cmp);
}
cnt = 0;
dfs2(1);
int pos = 0;
for (int i = 1; i <= m;i++){
while(anss[pos]!=ep[i]&&pos<n){
pos++;
}
}
if (pos >= n)
{
cout << "BAD GUGU" << endl;
}
else{
cout << "NOT BAD" << endl;
}
}
return 0;
}
I Childhood dream
题意：
给出n个串，每个串还对应两个提示a和b，a代表这个提示串和正确答案有多少位置上的数是相同的，b代表有多少是数字相同但是位置不同的
思路：
没想到直接纯爆搜即可，题目说的是提示串中每个数字都是不同的，但是没有说答案串中都是不同的，但所有的题解都是按照答案串中数字都不同处理，不知道为什么，可能是题目不严谨把....
#include<bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
int n, m,tips[N][15],A[N],B[N],vis[15],res[15];
bool check(){
for (int i = 0; i < n;i++){
int a = 0, b = 0;
for (int j = 0; j < m;j++){
if(res[j]==tips[i][j]){
a++;
}
else {
for (int k = 0; k < m;k++){
if(res[j]==tips[i][k]){
b++;
break;
}
}
}
}
if(a!=A[i]||b!=B[i]){
return false;
}
}
return true;
}
bool dfs(int step){
if(step==m){
//cout << 1 << endl;
if(check()){
for (int i = 0; i < m;i++){
cout << res[i];
}
cout << endl;
return true;
}
else{
return false;
}
}
for (int i = 0; i <= 9;i++){
if(vis[i])
continue;
vis[i] = 1;
res[step] = i;
if(dfs(step + 1)){
//cout << i << endl;
return true;
}
vis[i] = 0;
}
return false;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n;i++){
for (int j = 0; j < m;j++){
scanf("%1d", &tips[i][j]);
}
scanf("%d%d", &A[i], &B[i]);
}
dfs(0);
return 0;
}
J THE END IS COMING!!!!!
不会，咕咕咕