1003 Inversion

Inversion

需要统计的区间最大值次数是$O(n\log (n))$级别的。时间复杂度$O(n\log (n))$。优秀的多个$O(\log (n))$的做法也是可以卡过的。

这里介绍一下优雅的暴力做法。将AA数组按值从大到小排序，对于每个下标$i$暴力找到最大的不被iii整除的数。时间复杂度O(nlog(n))。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

struct pp{
    int number,val;
    bool operator <(pp const&b)const{
        return val<b.val;
    }
}a[100005];

vector<int>hello;

int main(){
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            int n;
            hello.clear();
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i].val);
                a[i].number=i;
            } 
            sort(a+1,a+n+1);
            for(int i=2;i<=n;i++){
                int maxn=0;
                for(int j=n;j>=1;j--){
                    if(a[j].number%i!=0){
                        hello.push_back(a[j].val);
                        break;
                    }
                }    
            }
            for(int i=0;i<hello.size();i++){
                if(i>0)printf(" ");
                printf("%d",hello[i]);
            }
            printf("\n");
        }
    }
    return 0;    
}

1008 Kirinriki

Kirinriki

标题提示我们回文串。

两个不重合的子串向中心一起延长会形成奇偶长度两种合串。枚举一下中心向外延伸，如果和超过了阈值弹掉中心处的位置。双指针维护。时间复杂度O(n​2​​)

另解：枚举[1,i],[j,n]用同样方法往内缩。时间复杂度O(n​2​​)

老司机队做法：发现所选元素肯定是在对角线上的元素，那么我们就遍历两条对角线 来看一看满足长度为m的最大长度是多少

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 8010;
char in[maxn];
//int dis[maxn][maxn];
queue<int> que;
int main(){
    //freopen("input.txt", "r", stdin);
    int t;
    int i,j,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&m);
        scanf("%s",in+1);
        int len = strlen(in+1);
        int save;
        int sum,res = -1;
        for(i=1;i<len;i++){
            int x = i, y = i;
            sum = 0;
            //from dis[i][i]
            while(!que.empty()){
                que.pop();
            }
            x--,y++;
            while(x>=1&&y<=len){
                save = abs(in[x]-in[y]);
                que.push(save);
                sum += save;
                while(sum>m){
                    sum -= que.front();
                    que.pop();
                }
                x--, y++;
                int killme = que.size();
                res = max(res,killme);
                //cout<<"push "<<save<<" "<<que.size()<<" "<<sum<<" "<<res<<endl;
            }
            
            //from dis[i][i+1]
            x = i, y = i+1;
            sum = 0;
            while(!que.empty()){
                que.pop();
            }
            while(x>=1&&y<=len){
                save = abs(in[x]-in[y]);
                que.push(save);
                sum += save;
                while(sum>m){
                    sum -= que.front();
                    que.pop();
                }
                x--, y++;
                int killme = que.size();
                res = max(res,killme);
                //cout<<"push "<<save<<" "<<que.size()<<" "<<sum<<" "<<res<<endl;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

1010 Gameia（待补）

• 如果Bob能把这棵树分成若干两个一组的点对，那么Bob取得胜利，否则Alice获胜。
• 如果原树不存在两两匹配的方案，Alice从树叶开始，每次都染树叶父节点，Bob被迫只能不断的染叶子，Bob退化成一般玩家，因为Bob做不做小动作都不会逆转局势，总会出现一个时间点Bob没办法跟上Alice的节奏而让Alice染到一个周围都已被染色的孤立点（因为原树不存在两两匹配的方案）
• 如果原树存在两两匹配的方案，而且Bob的小动作次数也足以把原树分成两两的点对，那么Bob显然获胜。
• 如果原树存在两两匹配的方案，而Bob的小动作不足以把树分成两两的点对，Alice一定获胜，因为每次染某个叶子节点（该节点为其父节点的唯一子节点），Alice总能迫使Bob不断的做小动作以保证剩下的树不会出现奇数节点的树，且每次小动作割出一个点对（包含Alice刚染的点），最后有两种情况。
• 出现某个结点有>=2个子节点为叶子节点。Alice染这个点，Bob跟不上Alice的节奏，出现孤点，Ailice取胜
• 否则整个过程一定会持续到树被染光或者Bob被Alice掏空导致做不了小动作进而被迫割出一块size为奇数的子树（这棵树显然没办法两两匹配）而败北。
• Bob被允许“任意时刻”做小动作看似很厉害其实很鸡肋，把问题改成“Bob只能在游戏开始之前做小动作”会得到同样的结论。
• “氪不改命，玄不救非”

时间复杂度 O(n)O(n)O(n)

1011 Classes

唯一的trick是要判一下Venn图上每个部分不小于0。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int classes[110][10];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(classes,0,sizeof(classes));
        int n;
        scanf("%d",&n);
        for(int i = 1; i <= n ;i ++)
        {
            for(int j = 1; j <= 7 ;j ++)
            {
                scanf("%d",&classes[i][j]);
            }
        }
        
        int maxNum = 0;
        for(int i = 1; i <= n ;i ++)
        {
            if(classes[i][1] >= classes[i][4] && classes[i][1] >= classes[i][6])
            {
                if(classes[i][2] >= classes[i][4] && classes[i][2] >= classes[i][5])
                {
                    if(classes[i][3] >= classes[i][5] && classes[i][3] >= classes[i][6])
                    {
                        if(classes[i][5] >= classes[i][7] && classes[i][4] >= classes[i][7] && classes[i][6] >= classes[i][7])
                        {
                            if(classes[i][2] - classes[i][4] - classes[i][5] + classes[i][7] >=0)
                            {
                                if(classes[i][1] - classes[i][4] - classes[i][6] + classes[i][7] >=0)
                                {
                                    if(classes[i][3] - classes[i][5] - classes[i][6] + classes[i][7] >=0)
                                    {
                                        int temp = 0;
                                        for(int j = 1; j <= 3; j++)
                                            temp += classes[i][j];
                                            
                                        for(int j = 4; j <= 6; j++)
                                            temp -= classes[i][j];                            
                                
                                        temp += classes[i][7];    
                                            
                                        maxNum = max(maxNum,temp);    
                                    }
                                }
                            }
                        
                
                        }
                        
                    }
                }
            }
        }
        
        printf("%d\n",maxNum);
    }
    
    return 0;
 }