头像

lrx2020




离线:1天前


最近来访(6)
用户头像
Ethanyyc
用户头像
hqyang
用户头像
yxc的小迷妹
用户头像
Hacker_King
用户头像
Lengyu


lrx2020
3天前

C++ 对拍 (转载)

https://www.cnblogs.com/EdisonBa/p/13509379.html

对拍是什么

​对拍,是一个比较实用的工具。它能够非常方便地对于两个程序的输出文件进行比较,可以帮助我们实现一些自动化的比较输出结果的问题。

​众所周知,每一道编程题目,都会有某种正解能拿到满分;当我们想不出正解时,我们往往可以打暴力代码来获取部分分数。

​但是,当我们觉得有思路写正解,但又担心自己正解写的不对,而恰好,我们又有一个能够暴力骗分的代码。这个时候就可以用到对拍。 暴力骗分代码必须保证正确性,最多只是超时,不能出现答案错误的情况。

​这样,我们可以造多组数据,让暴力骗分的程序跑一遍,再让我们自己写的正解跑一遍,二者进行多次对比。如果多组数据都显示二者的输出结果一样,那么这个正解大概率没问题。相反地,如果两组数据不同,我们就找到了一组错误数据,方便调试,找到正解哪里出了问题。

​这便是对拍。其作用也在上文提出。

对拍的实现

​首先,我们要有2份代码,一份是这一道题“你写的正解”代码,另一份是同一道题“你打的暴力”代码。

​为了方便,我们先用 A+B problem 来演示对拍。

​自己的代码: std.cpp

#include <cstdio>
using namespace std;
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

​暴力代码:baoli.cpp

#include <cstdio>
using namespace std;
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int ans = 0;
    int i;
    for (i = 1; i <= a; i++)
        ans++;
    for (i = 1; i <= b; i++)
        ans++;
    printf("%d\n", ans);
    return 0;
}

两份代码有了,我们把它放在同一个文件夹里。这样算是做好了对拍的准备。

制作数据生成器

​这样,我们可以造多组数据,让暴力骗分的程序跑一遍,再让我们自己写的正解跑一遍,二者进行多次对比。如果多组数据都显示二者的输出结果一样,那么这个正解大概率没问题。相反地,如果两组数据不同,我们就找到了一组错误数据,方便调试,找到正解哪里出了问题。

​这便是对拍。其作用也在上文提出。

对拍的实现#
准备基本代码#
​首先,我们要有2份代码,一份是这一道题“你写的正解”代码,另一份是同一道题“你打的暴力”代码。

​为了方便,我们先用 A+B problem 来演示对拍。

​自己的代码: std.cpp

#include <cstdio>
using namespace std;
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

​暴力代码:baoli.cpp

#include <cstdio>
using namespace std;
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int ans = 0;
    int i;
    for (i = 1; i <= a; i++)
        ans++;
    for (i = 1; i <= b; i++)
        ans++;
    printf("%d\n", ans);
    return 0;
}

​两份代码有了,我们把它放在同一个文件夹里。这样算是做好了对拍的准备。

制作数据生成器

​我们制作的数据要求格式和上面两份代码的输入格式一样。

​根据上面,我们可以知道输入的数据为2个数,中间有空格分隔。那么,我们的数据生成器就要输出2个数,中间也要用空格分隔。

#include <cstdio>
#include <cstdlib>
#include <ctime>
int main()
{
    srand(time(0));
    //这是一个生成随机数随机种子,需要用到 ctime 库
    printf("%d %d\n", rand(), rand());
    //这样就生成了2个随机数
    return 0;
}

对拍代码

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe > in.txt");
        system("baoli.exe < in.txt > baoli.txt");
        system("std.exe < in.txt > std.txt");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
    return 0;
}



分享 骗分导论

lrx2020
3天前

1.1 无解情况

当题目中出现,若无解请输出“-1”,看到这句话时,骗分就欣喜若狂,因为——数据中必定会有无解的情况!那么,只要打出下面这句话:

cout << "-1" << end;

就能得到10分,甚至20分,30分!

1.2 样例

每道题目的后面,都有一组“样例输入”和“样例输出”。它们的价值极大,不仅能初步帮你检验程序的对错(特别坑的样例除外),而且,如果你不会做这道题,你就可以直接输出样例!

2.1 模拟

所谓模拟,就是用计算机程序来模拟实际的事件。例如NOIP2012的“寻宝”,就是写一个程序来模拟小明上藏宝塔的动作。

2.2 DFS

这对于你的骗分是至关重要的。比如说,一些动态规划题,可以DFS;数学题,可以DFS;剪枝的题,更能DFS。

例题:NOIP2003,采药

题目描述 Description

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?

输入描述 Input Description

输入第一行有两个整数T(1<=T<=1000)和M(1<=M<=100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出描述 Output Description

输出包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

样例输入 Sample Input

70 3
71 100
69 1
1 2
样例输出 Sample Output

3
数据范围及提示 Data Size & Hint

对于30%的数据,M<=10;

对于全部的数据,M<=100。

这题的方法很简单。我们瞄准20%的数据来做,可以用DFS枚举方案,然后模拟计算出最优解。附一个大致的代码:

void DFS(int d,int c){
    if(d==n){if(c>ans)ans=c; return;}
    DFS(d+1,c+w[i]);
    DFS(d+1,c);
}

3.1 输出随机数

如果你觉得你的人品很好,可以试试这一招——输出随机数。
先看一下代码:

#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));
//输出随机数前执行此语句
printf("%d",rand()%X);
//输出一个0~X-1的随机整数。

这种方法适用于输出一个整数(或判断是否)的题目中,答案的范围越小越好。让老天决定你的得分吧。
据说,在NOIP2013中,有人最后一题不会,愤然打了个随机数,结果得了70分啊!!

3.2 猜测答案

有些时候,问题的答案可能很有特点:对于大多数情况,答案是一样的。这时,骗分就该出手了。你需要做的,就是发掘出这个答案,然后直接输出。
有时,先写出朴素算法,然后造一些数据,可能就会发现规律。

3.3 打表

NOIP2003 栈

题目描述 Description

栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。

栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙

宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。

现在可以进行两种操作,

1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)

2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2 3生成序列2 3 1的过程。(原始状态如上图所示) 。

你的程序将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。

输入描述 Input Description

输入文件只含一个整数n(1≤n≤18)

输出描述 Output Description

输出文件只有一行,即可能输出序列的总数目

样例输入 Sample Input

3
样例输出 Sample Output

5

这题看似复杂,但数据范围太小,N<=18。所以,骗分程序就好写了:

int a[18]={1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};

scanf("%d",&n);

printf("%d",ans[n-1]);

测试结果不言而喻,AC了。

4.1 贪心算法

给你一堆纸币,让你挑一张,相信你一定会挑面值最大的。其实,这就是贪心算法。
贪心算法是个复杂的问题,但你不用管那么多。我们只关心骗分。给你一个问题,让你从一些东西中选出一些,你就可以使用贪心的方法,尽量挑好的。

4.2贪心地得分

我们已经学了很多骗分方法,但他们中的大多效率并不高,一般能骗10~20分。这不能满足我们的贪心。
然而,我们可以合成骗分的程序。举个最简单的例子,有些含有无解情况的题目,它们同样有样例。我们可以写这个程序:

if(是样例) printf(样例);
else printf("-1");

这样也许能变10分为20分,甚至更多。

神奇方法

当然,合并骗分方法时要注意,不要重复骗同一种情况,或漏考虑一些情况。
至此,我已介绍完了我所知的骗分方法。如果上面的方法都不奏效,我也无能为力。但是,我还有最后一招——
有句古话说:“宁为玉碎,不为瓦全”。我们也应有这样的精神。骗不到分,就报复一下,卡评测以泄愤吧!
卡评测主要有两种方法:一是死循环,故意超时;二是进入终端,卡住编译器。
先介绍下第一种。代码很简单,请看:

while(1);

就是这短短一句话,就能卡住评测机长达10s,20s,甚至更多!对于测试点多、时限长的题目,这是个不错的方法。
第二种方法也很简单,但危害性较大,建议不要在重要比赛中使用,否则可能让你追悔莫及。它就是:

#include<con>  
//(windows系统中使用)

//或

#include</dev/console> 
//(Linux系统中使用)

它非常强大,可以卡住评测系统,使其永远停止不了编译你的程序。唯一的解除方法是,工作人员强行关机,重启,重测。当然,我不保证他们不会气愤地把你的成绩变成0分。请慎用此方法。

结语

不骗分,是骗分的最高境界!




lrx2020
4天前

60分做法

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int a[N];

int main() {
    deque<int> d;
    vector<int> v1;
    vector<int> v2;
    int n, k, minx, maxx;
    cin >> n >> k;
    minx = INF;
    maxx = -INF;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) {
        d.push_back(a[i]);
        minx = min(a[i], minx);
        maxx = max(a[i], maxx);
    }
    v1.push_back(minx);
    v2.push_back(maxx);
    for (int i = k + 1; i <= n; i++) {
        d.pop_front();
        d.push_back(a[i]);
        minx = INF, maxx = -INF;
        deque<int>::iterator it;
        for (it = d.begin(); it != d.end(); it++) {
            minx = min(minx, *it);
            maxx = max(maxx, *it);
        }
        v1.push_back(minx);
        v2.push_back(maxx);
    }
    vector<int> ::iterator it1, it2;
    for (it1 = v1.begin(); it1 != v1.end(); it1++) cout << *it1<< " ";
    puts("");
    for (it2 = v2.begin(); it2 != v2.end(); it2++) cout << *it2 << " ";
    return 0;
}

100分做法

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int a[N];

int main() {
    deque<int> d;
    vector<int> v1;
    vector<int> v2;
    int n, k, minx, maxx;
    cin >> n >> k;
    minx = INF;
    maxx = -INF;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) {
        d.push_back(a[i]);
        minx = min(a[i], minx);
        maxx = max(a[i], maxx);
    }
    v1.push_back(minx);
    v2.push_back(maxx);
    for (int i = k + 1; i <= n; i++) {
        d.pop_front();
        d.push_back(a[i]);
        minx = INF, maxx = -INF;
        deque<int>::iterator it;
        for (it = d.begin(); it != d.end(); it++) {
            minx = min(minx, *it);
            maxx = max(maxx, *it);
        }
        v1.push_back(minx);
        v2.push_back(maxx);
    }
    vector<int> ::iterator it1, it2;
    for (it1 = v1.begin(); it1 != v1.end(); it1++) cout << *it1<< " ";
    puts("");
    for (it2 = v2.begin(); it2 != v2.end(); it2++) cout << *it2 << " ";
    return 0;
}


分享 模板 堆

lrx2020
4天前

模板 堆

#include <iostream>
#include <queue>

using namespace std;

int main(){
    freopen("main.in","r",stdin);
    freopen("main.out","w",stdout);
    priority_queue<int,vector<int> > q;
    int n;
    cin >> n;
    while(n--){
        int a,b;
        cin >> a;
        if(a==1){
            cin >> b;
            q.push(-1*b);
        } 
        if(a==2) cout << -1*q.top() << endl;
        if(a==3) q.pop();
    }
    return 0;
} 



lrx2020
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5001, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("orz");
    else printf("%d\n", t);

    return 0;
}



活动打卡代码 AcWing 3726. 调整数组

lrx2020
5天前
#include<iostream>
using namespace std;

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;
        int a=0,b=0;
        while(n--)
        {
            int x;
            cin>>x;
            if(x&1)a++;
            else b++;
        }
        if(a==0||b==0)puts("YES");
        else puts("NO");
    }
}




lrx2020
5天前

模板 埃式筛法

#include <iostream>
#include <cstring>
#include <vector>
#define int long long

using namespace std; 
const int N = 1e9+10;
bool v[N];
vector<int> s;
vector<int>::iterator it;

void prime(int n){
    memset(v,0,sizeof v);
    for(int i=2;i<=n;i++){
        if(v[i]) continue;
        s.push_back(i);
        for(int j=i;j<=n/i;j++) v[i*j] = 1;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("result.out","w",stdout);
    int n;
    cin >> n;
    prime(n);
    for(it=s.begin();it!=s.end();it++) cout << *it << " ";
    return 0;
}



lrx2020
5天前

模板 并查集

#include <iostream>

using namespace std;
const int N = 100010;
int p[N];

int find(int x){
    if(p[x]==x) return x;
    else return p[x] = find(p[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) p[i] = i;
    while(m--) {
        int a,b,c;
        cin >> a >> b >> c;
        if(a==1) {
            p[find(b)] = find(c);
        }
        if(a==2) {
            if(find(b) == find(c)) cout << "Y" << endl;
            else cout << "N" << endl;
        }

    }

    return 0;
}



lrx2020
5天前

模板 快速幂与取余

快速幂
#include <iostream>
#define int long long

using namespace std;

int quickpow(int a,int b){
    int ans = 1;
    int base = a;
    while(b>0){
        if(b&1) ans *= base;
        base *= base;
        b >>=  1;
    }
    return ans;
}

signed main(){
    int a,b;
    cin >> a >> b;      
    cout << quickpow(a,b) << endl;
    return 0;
}
取余模板
#include <iostream>

using namespace std;

long long quickpow(long long a,long long b,long long c){
    long long ans = 1;
    long long base = a;
    while(b>0){
        if(b&1) {
            ans *= base;
            ans %= c;
        }
        base *= base;
        base %= c;
        b >>= 1;
    }
    return ans;
}

int main(){
    long long a,b,c;
    cin >> a >> b >> c;
    cout << quickpow(a,b,c) << endl;
    return 0;
}


活动打卡代码 AcWing 3661. 重置数列

lrx2020
6天前
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int Max = 0;
        int n, a[100010], b[100010], k; scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Max = max(Max, a[i]), b[i] = a[i];
        int ans = 0x3f3f3f3f;
        for (int c = 1; c <= Max; c++) {
            int res = 0;
            for (int i = 1; i <= n; i++) {
                if (b[i] == c) continue;
                res++;
                for (int j = i; j <= i + k - 1 && j <= n; j++) b[j] = c;
                i += k - 1;
            }
            ans = min(ans, res);
            for (int i = 1; i <= n; i++) b[i] = a[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}