链接：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 

1 31 44 1

样例输出1

120 题解：数学，找规律

#include 
       
        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
       

 

喵哈哈村的灯刀姐妹（二）

发布时间: 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

输出

输出最后剩下的运动员数量。

样例输入1 

31 22 33 2

样例输出1

2

题解：前缀，先位置排序，只要后方速度更大，前方标记，从前往后找最大速

#include 
       
        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
        
         >n){        memset(vis,0,sizeof(vis));        for(int i=0;i
         
          >f[i].x>>f[i].y;        sort(f,f+n,cmp);        int M=-1,ans=0;         for(int i=0;i
         
        
       

或

#include
       
        using namespace std;const int maxn = 1e5+7;pair
        
          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<
         
          <
         
        
       

喵哈哈村的灯刀姐妹（三）

发布时间: 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开始的。

样例输入1  

101 3 1 2 5 4 3 1 9 10

样例输出1

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 
       
        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
        
         >a[i];        for(int i=0;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
          
           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<
           
            <<" "<
            
             <
            
           
          
         
        
       

喵哈哈村的灯刀姐妹（五）

发布时间: 2017年4月9日 20:36   最后更新: 2017年4月9日 20:38   时间限制: 1000ms   内存限制: 128M

描述

喵哈哈村中的妖刀姬和青行灯是一对好姐妹，她们俩住在同一个屋檐下。

青行灯是个抖M，所以每天都回家装死，直到刀刀回答上她的问题后，她才会爬起来。

今天，她的问题是：

小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

输入

本题包含若干组测试数据。

每行一个整数n。

满足 1<=n<=1e18

输出

如果小明胜利输出XiaoMing。

否则输出XiaoHong。

样例输入1 

12

样例输出1

XiaoHongXiaoMing

题解：博弈论，n 为偶，A胜，否则，B胜。方块涂色，以1*2，2*1方块覆盖，看谁先封死

#include
       
        using namespace std;int main(){    long long n;    while(cin>>n){        if(n%2==0){            cout<<"XiaoMing"<