首页 > 代码库 > 喵哈哈村的灯刀姐妹
喵哈哈村的灯刀姐妹
链接：http://qscoj.cn/problem/67/
喵哈哈村的灯刀姐妹（一）
发布时间: 2017年4月9日 20:36 最后更新: 2017年4月9日 20:37 时间限制: 1000ms 内存限制: 128M
喵哈哈村中的妖刀姬和青行灯是一对好姐妹，她们俩住在同一个屋檐下。
青行灯是个抖M，所以每天都回家装死，直到刀刀回答上她的问题后，她才会爬起来。
今天，她的问题是：
给你l和r，判断有多少个x满足:
1.x是偶数
2.l<=x<=r
本题包含若干组测试数据。
每行两个整数l,r。
满足0<=l,r<=1e18
输出满足要求的x的个数。
1 3 1 4 4 1
1 2 0
题解：数学，找规律
#include <bits/stdc++.h> using namespace std; const int maxn=2005; int a[maxn],dp[maxn][maxn]; int main(){ long long l,r; while(cin>>l>>r){ int tot=0; if(r<l) cout<<"0"<<endl; else if(r%2&&l%2)cout<<((r-l)/2)<<endl; else cout<<((r-l)/2+1)<<endl; } }
喵哈哈村的灯刀姐妹（二）
发布时间: 2017年4月9日 20:36 最后更新: 2017年4月9日 20:37 时间限制: 1000ms 内存限制: 128M
喵哈哈村中的妖刀姬和青行灯是一对好姐妹，她们俩住在同一个屋檐下。
青行灯是个抖M，所以每天都回家装死，直到刀刀回答上她的问题后，她才会爬起来。
今天，她的问题是：
在一个一维坐标轴上，有n个运动员，每个运动员都朝着x轴正方向运动。第i个运动员的位置在x[i]，他的速度为y[i]，现在如果A超过了B，那么B就会消失。
请问过了很久很久之后，这个坐标轴上最后会剩下多少个运动员呢？
本题包含若干组测试数据。
第一行一个n，表示有n个运动员。
接下来n行，每行两个整数，分别表示x[i]和y[i]。
保证每个人的x[i]不一样。
满足1<=n<=100000,1<=x[i],y[i]<=1e9
输出最后剩下的运动员数量。
3 1 2 2 3 3 2
2
题解：前缀，先位置排序，只要后方速度更大，前方标记，从前往后找最大速
#include <bits/stdc++.h> using namespace std; const int maxn=100005; int vis[maxn]; struct m{ int x;int y; }; m f[maxn]; bool cmp(m a,m b){ return(a.x<b.x); } int main(){ int n; while(cin>>n){ memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++)cin>>f[i].x>>f[i].y; sort(f,f+n,cmp); int M=-1,ans=0; for(int i=0;i<n;i++){ if(f[i].y<M){ continue; } M=f[i].y; ans++; } cout<<ans<<endl; } }
或
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+7; pair<int,int> P[maxn]; int n; int main(){ while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++){ scanf("%d%d",&P[i].first,&P[i].second); } int Mx = -1; int Ans = 0; sort(P+1,P+1+n);//pair排序，先按第一维来排，再排第二维 for(int i=1;i<=n;i++){ if(Mx>P[i].second){ continue; } Mx = max(P[i].second,Mx); Ans++; } cout<<Ans<<endl; } }
喵哈哈村的灯刀姐妹（三）
发布时间: 2017年4月9日 20:36 最后更新: 2017年4月9日 20:37 时间限制: 1000ms 内存限制: 128M
喵哈哈村中的妖刀姬和青行灯是一对好姐妹，她们俩住在同一个屋檐下。
青行灯是个抖M，所以每天都回家装死，直到刀刀回答上她的问题后，她才会爬起来。
今天，她的问题是：
现在给你n个数，现在你需要找到一个最宽的先上升后下降的区间。
前提必须严格上升，严格下降哦。
本题包含若干组测试数据。
第一行一个n，表示数的个数。
第二行n个整数a[i]，表示每个数的大小。
满足：1<=n<=1e5,0<=a[i]<=1e9
输出区间的左右下标。
如果有多个最大区间，输出最左边的。
如果找不到输出-1 -1
注意 坐标是从0开始的。
10 1 3 1 2 5 4 3 1 9 10
2 7
题解：简单dp，前缀，分段考虑
eg: pos:0 1 2 3 4 5 6 7
num:1 2 3 4 5 2 1 3
dp1:1 2 3 4 5 1 1 2
dp2:1 1 1 1 3 2 1 1
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int a[maxn],dp1[maxn],dp2[maxn];//dp1[i]以i结尾的最长上升子序列 dp2[i] 以i开头的最长下降子序列 int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ if(a[i]>a[i-1]) dp1[i]=dp1[i-1]+1; else dp1[i]=1; } for(int i=n-1;i>0;i--){ if(a[i]>a[i+1]) dp2[i]=dp2[i+1]+1; else dp2[i]=1; } int ansl=-1,ansr=-1,Mx=1; for(int i=0;i<n;i++){ if(dp1[i]>1&&dp2[i]>1){ if(dp1[i]+dp2[i]>Mx){ Mx=dp1[i]+dp2[i]; ansl=i-dp1[i]+1; ansr=i+dp2[i]-1; } } } cout<<ansl<<" "<<ansr<<endl; } }
喵哈哈村的灯刀姐妹（五）
发布时间: 2017年4月9日 20:36 最后更新: 2017年4月9日 20:38 时间限制: 1000ms 内存限制: 128M
喵哈哈村中的妖刀姬和青行灯是一对好姐妹，她们俩住在同一个屋檐下。
青行灯是个抖M，所以每天都回家装死，直到刀刀回答上她的问题后，她才会爬起来。
今天，她的问题是：
小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？
本题包含若干组测试数据。
每行一个整数n。
满足 1<=n<=1e18
如果小明胜利输出XiaoMing。
否则输出XiaoHong。
1 2
XiaoHong XiaoMing
题解：博弈论，n 为偶，A胜，否则，B胜。方块涂色，以1*2，2*1方块覆盖，看谁先封死
#include<bits/stdc++.h> using namespace std; int main(){ long long n; while(cin>>n){ if(n%2==0){ cout<<"XiaoMing"<<endl; }else{ cout<<"XiaoHong"<<endl; } } }
喵哈哈村的灯刀姐妹