NOIP 2011 普及组 第三题 瑞士轮

认真读题很重要

简单分析


题目链接:[https://www.luogu.org/problemnew/show/P1309]
很容易发现,这道题目考察的排序,排序我们第一个肯定想到的是sort或者是归并排序,的确时间复杂度分别是O(n log2(n) )O(n log(n) )可如果是多次计算呢? 排除快排是因为不稳定性 所以总时间复杂度约为: sort O( r*2n^2*log2(2n) ) 归并 O( r*2n^2*log(2n) ) 看看数据范围emmmm 据说这样会 60 分,剩下的你懂的 所以我们需要优化 很显然sort已经没有优化的余地了,所以我们要从归并考虑 然后我们发现每次增减分的数组是单调的 也就是说我们只需要在开始的时候全部排序,后面我们每次只需要花O(n)的时间合并即可 这样子的时间复杂度约为:O( r*n^2 ) 稳如老狗啊!!!

代码


#include <cstdio>
#include <algorithm>
using namespace std;
int n,r,q;
struct node {
    int n,s,p;// n 号码 s 分数 p 能力
}a[210000],left[110000],right[110000];
int lcnt,rcnt,cnt,result_start;
// cmp 不解释
bool cmp(node a,node b){
    if(a.s==b.s) return a.n<b.n;
    else return a.s>b.s;
}
// 合并区间,参照归并排序
void marge(int left_start,int right_start){
    result_start=1;
    while(left_start<=n&&right_start<=n){
        if(cmp(left[left_start],right[right_start])) a[result_start++]=left[left_start++];
        else a[result_start++]=right[right_start++];
    }
    while(left_start<=n) a[result_start++]=left[left_start++];
    while(right_start<=n) a[result_start++]=right[right_start++];
}
int main(){
// 读入
    scanf("%d%d%d",&n,&r,&q);
    for(int i=1;i<=2*n;i++){scanf("%d",&a[i].s);a[i].n=i;}
    for(int i=1;i<=2*n;i++) scanf("%d",&a[i].p);
    sort(a+1,a+1+2*n,cmp);
    for(int i=1;i<=r;i++){
        lcnt=rcnt=0;// 模拟比赛过程
        for(int j=1;j<=2*n;j+=2){
            if(a[j].p>=a[j+1].p){
                a[j].s+=1;
                //printf("%d\n",++cnt);
                left[++lcnt]=a[j];right[++rcnt]=a[j+1];
            }
            else{
                a[j+1].s+=1;
                //printf("%d\n",++cnt);
                right[++rcnt]=a[j];left[++lcnt]=a[j+1];
            }
        }// 排序不解释
        if(i==1) sort(a+1,a+1+2*n,cmp);
        else marge(1,1);
    }
    printf("%d",a[q].n);
}

End


灵活运用每一种算法是一个非常重要的艺术 ]]>

论 dfs 与 bfs 的优化:NOIP 2017 普及组 第三题 – 棋盘

题目

参考题目:[https://www.luogu.org/problemnew/show/P3956]
相信大家都做过这道题吧,毕竟真的是到很明显的搜索/dp dp就不说了,有兴趣可以去题解去瞅瞅,不过因为有可能往回走,dp写起来会很麻烦让你怀疑你写的不是dp 但是同样是因为有可能回走,dfs与bfs无法进行像 bool x[][] 这样的剪枝办法(已经走过的路不走的办法) 所以就需要优化

骗分

既然是考试题目,那么我就就可以骗分

5 分


输出特殊状况—’-1′

10 分


在5分的情况下考虑输出0的情况

15-65 分


dfs大法,不加任何优化版 但是分数可能会有一定波动,需要注意下面几点
  • 尽可能递归 RE
  • 做一点微小的剪枝
  • 平时代码习惯不好可能会比较容易得低
  • 小心魔法
注意完以上几点,你就是一等大佬了

65 分


在15-65分做法中去除向上和向左,防止打转

100 分做法

博主在这里说两种搜索法-bfs/dfs 最短路以及dp大家有心情可以试试 这题用最短路这是杀鸡用牛刀 使用这两种方法都要建一个best[][]数组表当前最优花费,这样就可以避免一些不必要的地方,达成剪枝的目的。 先单独拿出来一行代码讲一下
col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col
可以转化为这个
int wh(){
    if(col[now.x][now.y]!=0) return col[now.x][now.y];
    else return temp.tu.col;
}
wh();
这个符号我们叫三目运算符/问号表达式

bfs


#include <cstdio>
#include <cstring>
using namespace std;
struct que{
    int tu_col,money,x,y;
// tu_col 目前变化的颜色
// money 目前所花钱数
// x y 目前走到(x,y)上
}q[110000];// q[] 队列
int n,m,x,y,c;
// dx[] dy[] 增量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
// best[i][j] 目前位于(i,j)的已知最优解
// col[i][j] (i,j)格子上的颜色
int main(){
    memset(best,0x3f,sizeof(best));// 初始化
// 读入
   scanf("%d%d",&m,&n);
   for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
// 加入队列首
    q[1].x=q[1].y=1;
    q[1].money=q[1].tu_col=0;
    int h,t;
    h=t=1;
    best[1][1]=0;// 第一个格子设为0
    while(h<=t){// 开始bfs
        que now;
        now=q[h];
// now 仅仅为了方便写,在下面的循环中可替换为q[h],也就是用于储存队列首
        for(int i=0;i<4;i++){// 模拟上下左右
            que temp=q[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            // temp 用于临时修改
            if(temp.x<=0||temp.y<=0||temp.x>m||temp.y>m) continue;// 判断越界
            if(col[temp.x][temp.y]==0/*如果当前格子上没有颜色*/&&temp.tu_col==0/*并且上一个格子没有用魔法*/){
                if(temp.money+2<best[temp.x][temp.y]){// 如果当前解优于已知最优解,才能放入队列
                    temp.money+=2;
                    temp.tu_col=col[now.x][now.y];// 存入临时颜色
                    q[++t]=temp;// 加入队列
                    best[temp.x][temp.y]=temp.money;// 更新 best 数组
                }
            }
            else if(col[temp.x][temp.y]!=0&&col[temp.x][temp.y]!=(col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col)){// 颜色不相等
                 if(temp.money+1<best[temp.x][temp.y]){// 不解释
                    temp.money+=1;
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
            else if(col[temp.x][temp.y]!=0){// 接下来只有可能颜色相等
                if(temp.money<best[temp.x][temp.y]){
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
        }
        h++;// 踢出对首
    }
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);// 不是预设值就输出
    else printf("-1");// 是预设值说明没有路通向那,输出-1
}

dfs


请参照 bfs 方法的注释来理解这个,所有变量含义一样
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,c;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
void dfs(int x,int y,int tu_col,int money){
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>m) continue;
        if(col[tx][ty]==0&&tu_col==0){
            if(money+2<best[tx][ty]){
                best[tx][ty]=money+2;
                dfs(tx,ty,col[x][y],money+2);
            }
        }
        else if(col[tx][ty]!=0&&col[tx][ty]!=(col[x][y]!=0?col[x][y]:tu_col)){
            if(money+1<best[tx][ty]){
                best[tx][ty]=money+1;
                dfs(tx,ty,0,money+1);
            }
        }
        else if(col[tx][ty]!=0){
            if(money<best[tx][ty]){
                best[tx][ty]=money;
                dfs(tx,ty,0,money);
            }
        }
    }
}
int main(){
    memset(best,0x3f,sizeof(best));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
    best[1][1]=0;
    dfs(1,1,0,0);
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);
    else printf("-1");
}

END

要是考场上没有删掉自己的dp就好了qwq ]]>

Caioj 1040:素数圈

0x01


  1. 判断素数
  2. 简单dfs

0x02


代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a[110],cnt;// a[] 储存顺序 cnt 临时储存和
bool x[110];//x[] 判重
// 判断质数
bool zs(int x){
    for(int i=2;i<=sqrt(x)+1;i++){
        if(x%i==0) return false;
    }
    return true;
}
// dfs部分
void dfs(int k){
    if(k==n+1){// 到达最终步骤
        if(!zs(a[n]+a[1])) return ;// 如果不是质数,那么下地狱吧
        // 输出
                for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    else{
        for(int i=2;i<=n;i++){
            if(!x[i]){
                cnt=a[k-1]+i; //求这个数与上个数的和
                if(zs(cnt)){// 求质数
                    a[k]=i;
                    x[i]=true;
                    dfs(k+1);
// 回溯
                    x[i]=false;
                    a[k]=0;
                }
            }
        }
    }
}
int main(){
// 输入
    scanf("%d",&n);
    a[1]=1;
    x[1]=true;
    dfs(2);// 目前已经确定第一个数为1(不然会重复)
}
]]>

Caioj 1034:二叉树的后序遍历

Start


原题题面: http://caioj.cn/problem.php?id=1037
这博客从我学oi前就有,,,这么现在逐渐有种要变成算法博客的趋势 咱的老师把这道题讲了似乎许多遍了,不管了,上题解

分析题目


emmm……不知道大家还记不记得,有一年的初赛就有过已知两中遍历求另一种遍历,不过那个题目是到选择,你可以动手试试,这道就需要我们找规律了,首先我们要知道,有一下两种情况
  1. 已知前序与中序遍历,求后序遍历
  2. 已知后序与中序遍历,求前序遍历
这两种状况是有唯一解的,其他的答案可能就会有多种 那么我们先看样例
ABDEHCFGI DBEHAFCIG
根据前序遍历的特性,我们可以轻松的找到A为根,那么我们在两种遍历中去掉A
BDEH CFGI DBEH FCIG
我们知道,中序遍历中,根节点左边是左子树部分,右边是有子树部分,让后我们就找到了左右子树 如果我们吧左子树在看成一个新的二叉树,那么继续搜下去,左后必然会精确到一个点,但是我们不知道要推多少次啊,怎么办?当然是递归

解析代码


先上代码
#include <cstdio>
#include <cstring>
using namespace std;
char a[110],b[110],x[110];//a字符串是前序遍历,b是中序遍历,x是后序遍历
int lx,k[110];
void dfs(int la,int ra,int lb,int rb){//la => 前序遍历左端点  la => 前序遍历左端点 ra => 前序遍历右端点  lb => 中序遍历左端点 rb => 中序遍历右端点 
    if(la>ra) return ;//等价与 if(lb>rb) return ; 如果你不理解,那么你可能还没有将题目读懂
    int temp_a=k[a[la]]-lb;//为什么要减去lb?因为我们要去找到他的位置,然而位置的开始搜索可能并不是0
    dfs(la+1,la+temp_a,lb,k[a[la]]-1);//往左子树找
    dfs(la+temp_a+1,ra,k[a[la]]+1,rb);//往右子树找
    x[lx++]=a[la];
}
int main(){
    scanf("%s",a);
    scanf("%s",b);//读入
    int lena=strlen(a);
    int lenb=strlen(b);//长度
    for(int i=0;i<lenb;i++) k[b[i]]=i;//因为我们要知道前序遍历中的一位在中序遍历中的哪一位,然而搜索有太费时间,所以我们存一下
    lx=0;//x字符串从0开始
    dfs(0,lena-1,0,lenb-1);//开始的步骤
    for(int i=0;i<lx;i++){
        printf("%c",x[i]);
    }
}

End


这道题目,,,,,,代码不难,思路特别的难,,所以,看脑子啦~ ]]>

NOIP PJ 2017 解题报告

Start


模拟测试:[https://www.luogu.org/contestnew/show/4468]
哇,幸亏普及组只有一天,要是提高组我怕是心态已经炸了23333 反正现在的局面很尴尬,因为大家的分数貌似差别都不大

T1 成绩


题目是真的水,不过出题人貌似还是给你了个坑(我差点就掉进去了 这个坑就是int的精度问题,估计dalao最容易死在这 直接上
#include <cstdio>
using namespace std;
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int cnt=a/10*2+b/10*3+c/10*5;
    printf("%d",cnt);
}

T2 图书管理员


至少在我眼里是到水题,数据范围那么小懒得写power,直接打表 当然能力次点的到底这么看的我就不知道了
#include <cstdio>
#include <algorithm>
using namespace std;
int mmp[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
//真 - 打表
int a[1100],b[1100][2];
int main(){
    int n,p;
    bool x;
    scanf("%d%d",&n,&p);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<p;i++) scanf("%d%d",&b[i][0],&b[i][1]);
    sort(a,a+n);//排序写起来方便点
//反正数据范围比较小
    for(int i=0;i<p;i++){
        x=false;
        for(int j=0;j<n;j++){
            if(a[j]%mmp[b[i][0]]==b[i][1]){
                       printf("%dn",a[j]);
                x=true;
                break;
            }
        }
        if(!x) printf("-1n");
    }
}

T3


T3写了好几种,基本上都炸,最后骗-1
2017.12.16 更新 最近学了会宽搜,发现宽搜还算简单的 直接上代码
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1<<27;
const int MAX_M=101;
const int MAX_N = 1001;
int chess[MAX_M][MAX_M];//棋盘,1代表红色,2代表黄色
int d[MAX_M][MAX_M]; //每个点到起点[1,1]的代价
int dx[]={0,-1,0,1,0};
int dy[]={0,0,1,0,-1};
int m; //棋盘实际的行和列
int n; //有颜色的个数
struct point{
    int x,y;
    int f_x,f_y; //来自哪个坐标
    int d; //距离起点的代价
};
queue<point> que; //bfs所需
bool inchess(int x,int y)
{
    if(x>=1&&x<=m&&y>=1&&y<=m)
        return true;
    return false;
}
//判断从点(p.x,p.y)到点(x,y)的代价
int getcost(int x,int y,point p)
{
    int f_x = p.x,f_y=p.y;
    if(chess[x][y]==0 && chess[f_x][f_y]==0) //都是空白
        return -1; //不可达
    if(chess[x][y]==0) return 2;
    if(chess[x][y]==chess[f_x][f_y]) return 0; //颜色相等
    if(chess[x][y]!=chess[f_x][f_y] && chess[f_x][f_y]!=0) return 1;
    if(chess[f_x][f_y]==0 && chess[x][y] != chess[p.f_x][p.f_y]) return 1;
    return 0;
}
int main()
{
    int ans=MAX;
    cin>>m>>n;
    for(int i=1;i<=m;i++) {fill(d[i],d[i]+m+1,MAX);fill(chess[i],chess[i]+m+1,0);}
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        chess[x][y] = c+1;
    }
    point p,p2;
    p.x =1; p.y=1; p.f_x=0;p.f_y=0; p.d = 0;
    que.push(p);
    d[1][1]=0;
    while(!que.empty()){
        p = que.front(); que.pop();
        if(p.x==m && p.y==m ){
            if(p.d<ans) ans=p.d;
            continue;
        }
        int x,y;
        for(int i=1;i<=4;i++){
            x=p.x+dx[i]; y=p.y+dy[i];
            if(inchess(x,y) && !(x==p.f_x && y==p.f_y)){
                 int cost = getcost(x,y,p);
                 if(cost==-1) continue;
                 p2.x=x; p2.y=y; p2.f_x=p.x; p2.f_y=p.y;
                 p2.d = p.d+cost;
                 if(p2.d<d[x][y]) {
                    d[x][y]=p2.d;
                     que.push(p2);
                }
            }
        }
    }
    if(ans!=MAX)     cout<<ans;
    else cout<<-1;
    return 0;
}

T4


T4直接骗-1 ~ 实际上T3那几种方法方法都比骗分拿的分高 ~

End


愿图灵祝我一力
]]>

Luogu P1056 排座椅- NOIP 2008 PJ T2

0x00


题目:点此跳转
有一位好心的同学说他这道题不会做,给了我,让后我就被他的好心折磨了许久

0x01


一开始,我的思路是个暴力,让后……就没有然后了,手打了一下,算了一下O(3n^2)…… 如果是真考试,暴力应该能水上几分

0x02


于是我直接一个桶排,输入前面几个直接按顺序输出 WA50, 和sort没啥关系
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d],x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min]++;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min]++;
        }
    }
    int temp=0;
    for(int i=1;i<m+1;i++){
        if(temp==k) break;
        if(x[i]>0) {temp++;printf("%d ",i);}
    }
    printf("\n");
    temp=0;
    for(int i=1;i<n+1;i++){
        if(temp==l) break;
        if(y[i]>0) {temp++;printf("%d ",i);}
    }
}

0x03


直到我看到有一句话,叫做上课时交头接耳的学生的对数最少, 我去你妈最少,害得我多加了两个
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct FUCK{
    int x,min;
};
int cmp(FUCK a,FUCK b){
    return a.min>b.min;
}
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d];
    FUCK x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min].min++;
            x[min].x=min;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min].min++;
            y[min].x=min;
        }
    }
    sort(y,y+n+10,cmp);
    sort(x,x+m+10,cmp);
    int a[k+1];
    int b[l+1];
    int temp=0;
    for(int i=1;i<m+1;i++){
        if(temp==k) break;
        if(x[i].min>0) {temp++;a[i]=x[i].x;}
    }
    temp=0;
    for(int i=1;i<n+1;i++){
        if(temp==l) break;
        if(y[i].min>0) {temp++;b[i]=y[i].x;}
    }
    sort(a+1,a+k+1);
    sort(b+1,b+l+1);
    for(int i=1;i<=k;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=1;i<=l;i++){
        printf("%d ",b[i]);
    }
}
WA 0这很尴尬 问题
  • 数组未清0
  • 输出未排序

0x04


改了上述两个点,以下是ac代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct FUCK{
    int x,min;
};
int cmp(FUCK a,FUCK b){
    return a.min>b.min;
}
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d];
    FUCK x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min].min++;
            x[min].x=min;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min].min++;
            y[min].x=min;
        }
    }
    sort(y,y+n+10,cmp);
    sort(x,x+m+10,cmp);
    int a[k+1];
    int b[l+1];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    int temp=0;
    for(int i=0;i<m+1;i++){
        if(temp==k) break;
        if(x[i].min>0) {temp++;a[i]=x[i].x;}
    }
    temp=0;
    for(int i=0;i<n+1;i++){
        if(temp==l) break;
        if(y[i].min>0) {temp++;b[i]=y[i].x;}
    }
    sort(a,a+k);
    sort(b,b+l);
    for(int i=0;i<k;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=0;i<l;i++){
        printf("%d ",b[i]);
    }
}

End


emmm……这题没啥技术含量,但是难想,这就比较尴尬 ]]>