牛客2021年愚人节比赛题解

有些奇奇怪怪的题不能保证分析是正确的……

A

啥都不干就好了。

#include <cstdio>

int main()
{

}

话说7秒AC的那个老哥确实离谱，这必是个大预言家（

B

需要通过诡异的手段获得系统时间，这些科技具体可以自己百度，这里提供一种（虽然我也不明白原理）：

#include<bits/stdc++.h>
#include <chrono>
#include <ctime>

using namespace std;

string getCurrentSystemTime()
{
    std::time_t secSinceEpoch = std::chrono::system_clock::to_time_t(std::chrono::system_clock::now());
    struct tm* calendarTime = localtime(&secSinceEpoch);
    char usrdefFormat[50]={0};
    strftime(usrdefFormat, 50, "%Y/%m/%d %H:%M:%S", calendarTime);
    return string(usrdefFormat);
}

int main()
{
    cout<<getCurrentSystemTime();
}

话说手写一个时间压点交居然一次都过不去……

C&I

其实就是要你套出这两题的输入然后交换一下输出。

话说从这两题极其离谱的提交次数就能猜出来一些东西吧qwq。

可以考虑手动枚举每一位，然后写一个程序判断这一位是否是某个数，如果是就让程序RE，这样就可以通过评测的返回结果来判断猜测是否正确，比如这样：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin>>s;
    if(s[3]=='a')return -1;
    return 0;
}

最后的答案分别是514和dbcac。

~~也有人说答案不是114就是514嘛……~~

当然你也可以考虑二分，不满足在某个范围就使它RE，总的思路精髓还是这个利用评测结果来判断的想法，其他的就无所谓了。

D

居然是一个正常的题。

但是是水题，全部模2加起来就是答案。没有什么坑。~~也许她说每种款式颜色大小均相同算一个小坑？~~

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;cin>>T;while(T--)
    {
        int n;cin>>n;int ans=0;
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            if(x&1)ans++;
        }
        cout<<ans<<"\n";
    }
}

E

枚举一下最后染成什么颜色，然后尝试将其他所有颜色的蝴蝶结染成那个颜色就好了。

但理论上你需要先将所有染色的方法跑一次floyd，然后再求解，但这样就会得到WA的好成绩，这也是我现在还没搞清楚的唯一一题。你需要去掉这个floyd才能AC。

~~也许是因为愚人节快乐？~~

#include <bits/stdc++.h>
#define fi first
#define se second
#define gc getchar() //(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define IT iterator
#define V vector
#define TP template <class o>
#define TPP template <typename t1, typename t2>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = b; i >= a; i--)
#define FOR(i, n) rep(i, 1, n)
#define debug(x) cerr << #x << ' ' << '=' << ' ' << x << endl
using namespace std;
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// char buf[1 << 20],*p1=buf,*p2=buf;
TP void qr(o& x) {
    char c = gc;
    x = 0;
    int f = 1;
    while (!isdigit(c)) {
        if (c == '-')
            f = -1;
        c = gc;
    }
    while (isdigit(c))
        x = x * 10 + c - '0', c = gc;
    x *= f;
}
template <class o, class... O> void qr(o& x, O&... y) {
    qr(x);
    qr(y...);
}
TP void qw(o x) {
    if (x / 10)
        qw(x / 10);
    putchar(x % 10 + '0');
}
TP void pr1(o x) {
    if (x < 0)
        x = -x, putchar('-');
    qw(x);
    putchar(' ');
}
template <class o, class... O> void pr1(o x, O... y) {
    pr1(x);
    pr1(y...);
}
TP void pr2(o x) {
    if (x < 0)
        x = -x, putchar('-');
    qw(x);
    putchar(10);
}
template <class o, class... O> void pr2(o x, O... y) {
    pr2(x);
    pr2(y...);
}

TP void cmax(o& x, o y) {
    if (x < y)
        x = y;
}
TP void cmin(o& x, o y) {
    if (x > y)
        x = y;
}

const int mod = 998244353;
TPP void ad(t1& x, t2 y) {
    x += y;
    if (x >= mod)
        x -= mod;
}
TPP void dl(t1& x, t2 y) {
    x -= y;
    if (x < 0)
        x += mod;
}


const int N = 110, inf = 2e9;
const ll INF = 1e15;
ll n, a[N], b[N][N];

void solve() {
    qr(n);
    FOR(i, n) qr(a[i]);
    memset(b, -1, sizeof b);
    int m, x, y;
    qr(m);
    while(m--) qr(x, y), qr(b[x][y]);
    ll ans = -1;
    FOR(i, n) {
        ll v = 0;
        FOR(j, n) if(i ^ j && a[j]) {
            if(b[j][i] == -1) {v = -1; break;}
            v += b[j][i] * a[j];
        }
        if(v != -1) {
            if(~ans) cmin(ans, v);
            else ans = v;
        }
    }
    if(ans == -1) puts("qcjj yyds");
    else pr2(ans);
}

int main() {
    int T = 1;
    qr(T);
    while (T--)
        solve();
    return 0;
}

F

答案是8 8 16。

三问的答案分三段给了，里面是自己的理解，可能不是很对，但实在找不到其他的了……

注意人是不算动物的，广播有说。

牛客的markdown不支持高亮，只能加粗凑合着看了。

Q1：

qcjj作为B站区的一位英语学习UP主，在今天开启了直播，背起了贯口——
在想当初，后汉三国有一位莽撞人。
自从桃园结义以来，大爷 姓刘名备字玄德，家住大树楼桑。二弟 姓关名羽字云长，家住山西蒲州解梁县。三弟 姓张名飞字翼德，家住涿州范阳郡。后续四弟，姓赵名云字子龙，家住镇定府常山县，百战百胜，后封为常胜将军。
只皆因长坂坡前，一场鏖战，赵云单人独马，闯进曹营，砍倒大纛两杆，夺槊三条。马落陷坑，堪堪废命。曹孟德 山头之上见一穿白小将、白盔、白甲、白旗靠、坐骑白龙马手使亮银枪，实乃一员勇将。心想，我若收服此将，何愁大事不成！
心中就有爱将之意，暗中有徐庶保护赵云，徐庶进得曹营一语未发，今日一见赵将军马落陷坑，堪堪废命，口尊：“丞相，莫非有爱将之意？”曹操言道：“正是。”徐庶言道：“何不收留此将？”曹操急忙传令：“令出山摇动，三军听分明，我要活赵云，不要死子龙。
倘有一兵一将伤损赵将军之性命，八十三万人马五十一员战将，与他一人抵命。”众将闻听不敢前进，只有后退。那赵云一仗怀揣幼主，二仗常胜将军之特勇，杀了个七进七出，这才闯出重围。
曹操一见，这样勇将焉能放走，在后面紧紧追赶，追至当阳桥前，张飞赶到，高叫：“四弟，不必惊慌，某家在此，料也无妨！”放过赵云的人马，曹操赶到不见赵云，只见一黑脸大汉立于桥上，曹操忙问 夏侯惇 ：“这黑脸大汉，他是何人？”夏侯言道：“他乃是张飞，一莽撞人。”
曹操闻听，大吃一惊，想当初关公在白马坡斩颜良之时，曾对某家言道，他有一结拜三弟，姓张名飞字翼德，在百万军中取上将之首如探囊取物，反掌观纹一般，今日一见，果然英勇。“撤去某家青罗伞盖，观一观那莽撞人武艺如何。”
青罗伞盖撤下，只见张飞豹头环眼，面如韧铁，黑中透亮，亮中透黑，颌下扎里扎煞一副黑钢髯，犹如钢针，恰似铁线，头戴镔铁盔，二龙斗宝，朱缨飘洒，上嵌八宝，云罗伞盖花冠于长，身披锁字大叶连环甲，内衬皂罗袍，足蹬虎头战靴，胯下马，万里烟云兽，手使丈八蛇矛。
站在桥头之上，咬牙切齿，捶胸愤恨，大骂：“曹操听真，呆，今有你家张三爷在此，尔等或攻，或战，或进，或退，或争，或斗，不攻，不战，不进，不退，不争，不斗，尔乃匹夫之辈。”大喊一声，曹兵退后；大喊二声，顺水横流；大喊三声，把当阳桥喝断。后人有诗赞之曰：“长坂坡前救赵云，喝退曹操百万军，姓张名飞字翼德，万古流芳莽撞人！”

Q2：

qcjj作为B站区的一位英语学习UP主，在今天开启了直播，背起了贯口——
在想当初，后汉三国有一位莽撞人。
自从桃园结义以来，大爷姓刘名备字玄德，家住大树楼桑。二弟姓关名羽字云长，家住山西蒲州解梁县。三弟姓张名飞字翼德，家住涿州范阳郡。后续四弟，姓赵名云字子龙，家住镇定府常山县，百战百胜，后封为常胜将军。
只皆因长坂坡前，一场鏖战，赵云单人独马，闯进曹营，砍倒大纛两杆，夺槊三条。马落陷坑，堪堪废命。曹孟德山头之上见一穿白小将、白盔、白甲、白旗靠、坐骑 白龙马 手使亮银枪，实乃一员勇将。心想，我若收服此将，何愁大事不成！
心中就有爱将之意，暗中有徐庶保护赵云，徐庶进得曹营一语未发，今日一见赵将军马落陷坑，堪堪废命，口尊：“丞相，莫非有爱将之意？”曹操言道：“正是。”徐庶言道：“何不收留此将？”曹操急忙传令：“令出山摇动，三军听分明，我要活赵云，不要死子龙。
倘有一兵一将伤损赵将军之性命，八十三万人马五十一员战将，与他一人抵命。”众将闻听不敢前进，只有后退。那赵云一仗怀揣幼主，二仗常胜将军之特勇，杀了个七进七出，这才闯出重围。
曹操一见，这样勇将焉能放走，在后面紧紧追赶，追至当阳桥前，张飞赶到，高叫：“四弟，不必惊慌，某家在此，料也无妨！”放过赵云的人马，曹操赶到不见赵云，只见一黑脸大汉立于桥上，曹操忙问夏侯惇：“这黑脸大汉，他是何人？”夏侯言道：“他乃是张飞，一莽撞人。”
曹操闻听，大吃一惊，想当初关公在白马坡斩颜良之时，曾对某家言道，他有一结拜三弟，姓张名飞字翼德，在百万军中取上将之首如探囊取物，反掌观纹一般，今日一见，果然英勇。“撤去某家青罗伞盖，观一观那莽撞人武艺如何。”
青罗伞盖撤下，只见张飞豹头环眼，面如韧铁，黑中透亮，亮中透黑，颌下扎里扎煞一副黑钢髯，犹如钢针，恰似铁线，头戴镔铁盔，二龙斗宝，朱缨飘洒，上嵌八宝，云罗伞盖花冠于长，身披锁字大叶连环甲，内衬皂罗袍，足蹬虎头战靴，胯下马，万里烟云兽，手使丈八蛇矛。
站在桥头之上，咬牙切齿，捶胸愤恨，大骂：“曹操听真，呆，今有你家张三爷在此，尔等或攻，或战，或进，或退，或争，或斗，不攻，不战，不进，不退，不争，不斗，尔乃匹夫之辈。”大喊一声，曹兵退后；大喊二声，顺水横流；大喊三声，把当阳桥喝断。后人有诗赞之曰：“长坂坡前救赵云，喝退曹操百万军，姓张名飞字翼德，万古流芳莽撞人！”

Q3：

qcjj作为B站区的一位英语学习UP主，在今天开启了直播，背起了贯口——
在想当初，后汉三国有一位莽撞人。
自从桃园结义以来，大爷姓刘名备字玄德，家住大树楼桑。二弟姓关名羽字云长，家住山西蒲州解梁县。三弟姓张名飞字翼德，家住涿州范阳郡。后续四弟，姓赵名云字子龙，家住镇定府常山县，百战百胜，后封为常胜将军。
只皆因长坂坡前，一场鏖战，赵云单人独马，闯进曹营，砍倒大纛两杆，夺槊三条。马落陷坑，堪堪废命。曹孟德山头之上见一穿白小将、白盔、白甲、白旗靠、坐骑白龙马手使亮银枪，实乃一员勇将。心想，我若收服此将，何愁大事不成！
心中就有爱将之意，暗中有徐庶保护赵云，徐庶进得曹营一语未发，今日一见赵将军马落陷坑，堪堪废命，口尊：“丞相，莫非有爱将之意？”曹操言道：“正是。”徐庶言道：“何不收留此将？”曹操急忙传令：“令出山摇动，三军听分明，我要活赵云，不要死子龙。
倘有一兵一将伤损赵将军之性命，八十三万人马五十一员战将，与他一人抵命。”众将闻听不敢前进，只有后退。那赵云一仗怀揣幼主，二仗常胜将军之特勇，杀了个七进七出，这才闯出重围。
曹操一见，这样勇将焉能放走，在后面紧紧追赶，追至当阳桥前，张飞赶到，高叫：“四弟，不必惊慌，某家在此，料也无妨！”放过赵云的人马，曹操赶到不见赵云，只见一黑脸大汉立于桥上，曹操忙问夏侯惇：“这黑脸大汉，他是何人？”夏侯言道：“他乃是张飞，一莽撞人。”
曹操闻听，大吃一惊，想当初关公在白马坡斩颜良之时，曾对某家言道，他有一结拜三弟，姓张名飞字翼德，在百万军中取上将之首如探囊取物，反掌观纹一般，今日一见，果然英勇。“撤去某家青罗伞盖，观一观那莽撞人武艺如何。”
青罗伞盖撤下，只见张飞豹头环眼，面如韧铁，黑中透亮，亮中透黑，颌下扎里扎煞一副黑钢髯，犹如钢针，恰似铁线，头戴镔铁盔，二龙斗宝，朱缨飘洒，上嵌八宝，云罗伞盖花冠于长，身披锁字大叶连环甲，内衬皂罗袍，足蹬虎头战靴，胯下马，万里烟云兽，手使丈八蛇矛。
站在桥头之上，咬牙切齿，捶胸愤恨，大骂：“曹操听真，呆，今有你家张三爷在此，尔等或攻，或战，或进，或退，或争，或斗，不攻，不战，不进，不退，不争，不斗，尔乃匹夫之辈。”大喊一声，曹兵退后；大喊二声，顺水横流；大喊三声，把当阳桥喝断。后人有诗赞之曰：“长坂坡前救赵云，喝退曹操百万军，姓张名飞字翼德，万古流芳莽撞人！”

G

显然是输出这7个数列的第n项。

第一个显然是 n
第二个显然是 2n-1
第三个显然是 $n^2$
第四个显然是 $2^{n-1}$
第五个显然是 $2^{2^{n-1}}$ ， $2^{n-1}$ 需要对 $mod-1$ 取模，原因参见费马小定理或欧拉定理。
第六个显然是 n%2
第七个不那么显然是 $\sum_{i=1}^n 10^{i-1}=\frac {10^n-1} {10-1}$ 。

应该没有什么坑点。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int mod=1000000007;
long long n;
int ksm(int x,long long y,int mod){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}

int main()
{
    scanf("%lld",&n);
    printf("%lld\n",n%mod);
    printf("%lld\n",(2*n-1)%mod);
    printf("%lld\n",n%mod*(n%mod)%mod);
    printf("%lld\n",ksm(2,n-1,mod));
    printf("%lld\n",ksm(2,ksm(2,n-1,mod-1),mod));
    printf(n&1?"1\n":"2\n");
    printf("%lld\n",1ll*(ksm(10,n,mod)+mod-1)*ksm(9,mod-2,mod)%mod);
}