考完后花了大概两天时间把除了 tg T4 以外的所有题全部都做出来了，其实老实说，没有什么不会的算法或是数据结构（包括 T4？），但思维难度确实还是有一点大，像我这种平时不怎么练思维，光会写一些数据结构模板题或是刷水题的蒟蒻还是很难拿到高分的，还有就是一些细节很多，没注意到就很容易凉凉，所以总体来说虽然 tg 把两天改成了一天，但确实还是有区分度的把我这种菜鸡区分出来了，pj 还是可以，题目难度可能比去年稍稍难一点，但也不算很难，还是在意料之中。

题面

PJ

pj 主要是 T3 难想一点，然后 T4 是个 DP（居然没有图论！？），其他两个题就比较常规了，T1 还是 sb 签到题，T2 暴力的话很好写，但必须考虑优化，跟去年 T2 一样。

T1 优秀的拆分

签到题，首先看到若干个不同的 22 的正整数次幂之和可以很快想到跟位运算有关，看完题面之后果然没错。

由于必须要是正整数次幂，那就代表 nn 的二进制下的第 00 位不能为 11，也就是说只要是奇数就输出 −1-1，否则就一位一位找，如果某一位为 11，就拿个东西记录一下，最后倒序输出即可。

我考试的时候用的是 lowbit，如果不会的话请左转这篇文章。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
int n,k,ans[100];
int main()
{
    scanf("%d",&n);
    if(n&1)
        printf("-1");
    else
    {
        for(;n;n-=lowbit(n))
            ans[++k]=lowbit(n);
        for(int i=k;i>=1;i--)
            printf("%d ",ans[i]);
    }
    return 0;
}

T2 直播获奖

一个简单的求第 K 大值的问题，方法很多，比较常见的是用个桶来记录每种成绩的数量，然后从后往前找第 K 个就好了，但时间复杂度为 O(600n)O(600n)（好吧这个表述可能有一点点问题，但这个常数是真的不能忽略啊喂），10510^5 的数据有可能会被卡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,w,a[N],num[1010];
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)
    {
        int t=max(1,i*w/100);
        scanf("%d",&a[i]);
        num[a[i]]++;
        for(int j=600,k=0;j>=0;j--)
            if(k+num[j]>=t)
            {
                printf("%d ",j);
                break;
            }
            else
                k+=num[j];
    }
    return 0;
}

我们还有另外的方法来做这道题，考虑一个暴力算法，即每次对序列进行排序，然后输出第 K 项，我们发现插入排序可以很好地对序列进行维护，但美中不足的是它的单次复杂度还是 O(n)O(n)，这是个大问题，所以，我们可以尝试用一个 vector 来实现类似的功能，每次用 lower_bound 找到应该插入的位置，然后直接 insert 进去，我在考场上用的就是这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,w;
vector<int> num;
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)
    {
        int t=max(1,i*w/100)-1,a;
        scanf("%d",&a);
        num.insert(lower_bound(num.begin(),num.end(),a),a);
        printf("%d ",num[num.size()-1-t]);
    }
    return 0;
}

但老实说这种方法的复杂度很玄学，因为据一些大佬所说，insert 的时间复杂度并不是我在考试时以为的 O(1)O(1)，而是 O(n)O(n)，但由于常数极小，所以可以近似地看成 O(log⁡n)O(\log n)（这里可能有误，欢迎各位大佬指正），另外，由于这道题数据规模还不是很大，所以没有被卡。

事实上，这道题存在一个 O(nlog⁡n)O(n\log n) 的做法不是我在考试时的那种玄学操作，即用一个对顶堆维护第 K 大值。

对顶堆的原理比较有趣，我们用两个堆，一个是小根堆，一个是大根堆，这道题要求维护的是第 K 大值，对于每一个新插入的数 xx，我们进行如下操作：

  1. 将 xx 与小根堆堆顶元素 yy 比较，如果 xx 大于 yy，则把 xx 塞进小根堆里，反之，则把 xx 塞进大根堆里。
  2. 若小根堆里的数的数量小于 K，则把大根堆堆顶元素塞进小根堆里，并弹出，如此反复，直到小根堆里的数的数量等于 K。
  3. 若小根堆里的数的数量大于 K，则把小根堆堆顶元素塞进大根堆里，并弹出，如此反复，直到小根堆里的数的数量等于 K。
  4. 此时小根堆堆顶元素即为答案。

这个过程还是比较好想的，就像是把这个数列分成了两段，其中一段包含了最大的 K 个数，另外一段包含了其余的，当发现前一段的数的数量小于 K 时，就把后一段里最大的数划给前一段，反之则把前一段里最小的数划给后一段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n,w,a;
priority_queue<int> p;
priority_queue< int,vector<int>,greater<int> > q;
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)
    {
        int t=max(1,i*w/100);
        scanf("%d",&a);
        if(q.empty()||a>q.top())
            q.push(a);
        else
            p.push(a);
        while(q.size()<t)
        {
            q.push(p.top());
            p.pop();
        }
        while(q.size()>t)
        {
            p.push(q.top());
            q.pop();
        }
        printf("%d ",q.top());
    }
    return 0;
}

当然你要是实在闲着没事干的话平衡树也能很好地解决这道题，就是码量较上面这三种写法可能大了不少，不过时间复杂度也是比较优秀的 O(nlog⁡n)O(n\log n)。

T3 表达式

这道题是一道字符串的模拟题，要求求一个后缀逻辑表达式的值，后缀表达式的求解就不赘述了，可以参考 OI Wiki，这里主要讲一下如何快速求出反转变量的值后表达式的值。

首先，由于这是一个逻辑表达式，所以其值只有可能为 00 或 11，换句话说，如果我们知道它的值不为 00，那它就一定为 11，这对里面的每一个变量都同样适用。

其次，每个变量都只出现一次，所以即使反转某个变量的值，也不可能出现某个运算符两边的值同时反转的情况。

最后，询问之间相互独立，也就是说我们每一次只用考虑一个变量的值的改变即可。

有这几点之后，结论就比较清晰了，我们可以预处理出哪些变量的值反转后会影响到整个表达式的值（这里我将其称为“关键的变量”），如果某次询问反转的是一个关键的变量的值，那么整个表达式的值一定会被反转。

接下来我们考虑如何求出这些变量，可以分两种情况讨论。

  1. 与运算符（x1∧x2x_1\land x2）
    • 如果 x1x_1 和 x2x_2 都为 11，则这个表达式的值为 11，此时不管反转哪个变量的值，表达式的值都会变成 00，所以 x1x_1 和 x2x_2 都是关键的。
    • 如果 x1x_1 和 x2x_2 只有一个为 11，则这个表达式的值为 00，此时如果把为 00 的那个变量的值反转，表达式的值就会变成 11，所以为 00 的那个变量是关键的，而如果为 11 的那个变量反转，表达式的值还是 00，所以为 11 的那个变量不是关键的。
    • 如果 x1x_1 和 x2x_2 都为 00，则不管反转哪个，表达式的值都为 00，所以它们都不是关键的。
  2. 或运算符（x1∨x2x_1\lor x_2）
    • 如果 x1x_1 和 x2x_2 都为 00，则这个表达式的值为 00，此时不管反转哪个变量的值，表达式的值都会变成 11，所以 x1x_1 和 x2x_2 都是关键的。
    • 如果 x1x_1 和 x2x_2 只有一个为 00，则这个表达式的值为 11，此时如果把为 11 的那个变量的值反转，表达式的值就会变成 00，所以为 11 的那个变量是关键的，而如果为 00 的那个变量反转，表达式的值还是 11，所以为 00 的那个变量不是关键的。
    • 如果 x1x_1 和 x2x_2 都为 11，则不管反转哪个，表达式的值都为 11，所以它们都不是关键的。

（至于取反运算符（¬x\lnot x）可以忽略，因为它是单目运算符，我们甚至可以直接把它取反的那个变量的值取反，然后删掉它，当然我个人不推荐这样，因为会多出许多代码）

容易发现，上述规则不仅适用于单个变量，也同样适用于表达式，即 x1x_1 和 x2x_2 可以是表达式，我们对这两个表达式分别求出它的关键的变量之后，在运算时按照上述规则进行判断，如果某个表达式是关键的，则它的所有关键的变量都是这个新表达式的关键的变量，反之则都不是，这样不停地对表达式进行合并，最后就能求出整个表达式的关键的变量和表达式的值，将其存在数组里排个序，在询问时 lower_bound 一下，判断反转的变量是否是关键的，如果是，就输出表达式值反转后的值，如果不是，直接输出原值即可，时间复杂度 O(∣s∣+qlog⁡n)O(|s|+q\log n)。

（看到很多大佬是对表达式建了棵树，然后打标记，可以做到 O(∣s∣)O(|s|)，然而我太弱了，考场上只想出来用栈来做，所以只好借助了 STL 的力量，而且时间复杂度比较**，常数也是能上天的那种，在 lg 上跑了整整 1.77s，所以强烈建议看完本篇题解后再看一下 lg 上的题解）

STL 操作较多，主要是用了很多 assign 和 insert，如果有疑问，请自行百度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s;
int n,q,len,tid,ans,x[N],p[N];
stack<int> num;
stack< vector<int> > val;
vector<int> k;
void solve()
{
    for(int i=0;i<len;i++)
    {
        if(s[i]==' ')
        {
            if(tid)
            {
                num.push(x[tid]);
                vector<int> tmp;
                tmp.push_back(tid);
                val.push(tmp);
            }
            tid=0;
        }
        else
        {
            if(s[i]=='x')
                tid=0;
            if(s[i]>='0'&&s[i]<='9')
                tid=tid*10+s[i]-'0';
            if(s[i]=='|')
            {
                int x1=num.top();
                num.pop();
                int x2=num.top();
                num.pop();
                num.push(x1|x2);
                vector<int> t1,t2,empty;
                t1.assign(val.top().begin(),val.top().end());
                val.pop();
                t2.assign(val.top().begin(),val.top().end());
                val.pop();
                if(!x1&&!x2)
                    t1.insert(t1.end(),t2.begin(),t2.end());
                if(!x1&&x2)
                    swap(t1,t2);
                if(!x1||!x2)
                    val.push(t1);
                else
                    val.push(empty);
            }
            if(s[i]=='&')
            {
                int x1=num.top();
                num.pop();
                int x2=num.top();
                num.pop();
                num.push(x1&x2);
                vector<int> t1,t2,empty;
                t1.assign(val.top().begin(),val.top().end());
                val.pop();
                t2.assign(val.top().begin(),val.top().end());
                val.pop();
                if(x1&&x2)
                    t1.insert(t1.end(),t2.begin(),t2.end());
                if(x1&&!x2)
                    swap(t1,t2);
                if(x1||x2)
                    val.push(t1);
                else
                    val.push(empty);
            }
            if(s[i]=='!')
            {
                int x1=num.top();
                num.pop();
                num.push(!x1);
            }
        }
    }
    ans=num.top();
    k.assign(val.top().begin(),val.top().end());
}
int main()
{
    getline(cin,s);
    len=s.size();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    solve();
    sort(k.begin(),k.end());
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int j;
        scanf("%d",&j);
        int t=lower_bound(k.begin(),k.end(),j)-k.begin();
        if(t<k.size()&&k[t]==j)
            printf("%d\n",ans^1);
        else
            printf("%d\n",ans);
    }
    return 0;
}

能想到用栈来存 vector 的恐怕也只有我了

T4 方格取数

从数据规模和题目名称可以看出来应该是一道 DP，可以用 dpi,jdp_{i,j} 表示走到第 ii 行 jj 列所能取到的最大的数字和，但由于这道题有可能从下面走到上面来，所以不能用传统的转移方式。

注意到这道题不能从右边走到左边，这启发我们一列一列地进行递推，具体来说，我们可以发现，从 (x−1,y1)(x-1,y_1) 走到 (x,y2)(x,y_2)，一定是先走到 (x,y1)(x,y_1)，再一路向上或向下走到 (x,y2)(x,y_2)，并收集从 (x,y1)(x,y_1) 到 (x,y2)(x,y_2) 的所有数字，因此，应该可以想到如下递推式

dpi,j=max⁡1≤k≤ndpk,j−1+{∑x=ikax,j−1(i≤k)∑x=kiax,j−1(i>k)dp_{i,j}=\max_{1\le k\le n} dp_{k,j-1}+\begin{cases}\sum_{x=i}^k a_{x,j-1}(i\le k)\\\sum_{x=k}^i a_{x,j-1}(i>k)\end{cases}

但如果对于每一个 dpi,jdp_{i,j} 都枚举一遍这个最大值的话，那么时间复杂度为 O(n2m)O(n^2m)，很明显不行，考虑优化。

可以发现，对于同一列的 dpi,jdp_{i,j}，这个枚举的过程会有很多重复的运算，我们可以用一个 mxmx 变量记录 dpi−1,jdp_{i-1,j} 所取到的最大的值，在此基础上得出 dpi,jdp_{i,j} 应取的最大值，先考虑第二种，即 i>ki>k 的情况，为了便于理解，这里放一张图片，阐述 dpi,jdp_{i,j} 的得出过程。

如图，这是已经求出的一个 dpi−1,jdp_{i-1,j}，而 dpi,jdp_{i,j} 的来源有两种。

可以看出，如果我们从 (k,j−1)(k,j-1) 走到 (k,j)(k,j) 是走到 (k,j)(k,j) 的最优方案，那么可以一直往下，中间不停地把方格里的值累加到 mxmx 里，直到遇到一个地方 (i,j)(i,j)，使得 dpk,j−1+∑x=kiax,j<dpi,j−1+ai,jdp_{k,j-1}+\sum_{x=k}^i a_{x,j}<dp_{i,j-1}+a_{i,j}，就说明这个地方从上一列走过来会更优，那我们就可以更新 mxmx 变量的值为 dpi,j−1+ai,jdp_{i,j-1}+a_{i,j}，并重复上述过程，而对于 i≤ki\le k 的情况也是一样的思路。

还有一点需要注意的地方，因为第 11 列不存在从上一列走过来的情况，我们需要进行预处理。

还有什么不明白的就看代码吧，个人感觉码风还是不错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
ll n,m,mx,a[N][N],dp[N][N];
int main()
{
    memset(dp,-0x3f,sizeof(dp));//初始化最小值
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
        dp[i][1]=a[i][1]+dp[i-1][1];//预处理第一列
    for(int j=2;j<=m;j++)
    {
        mx=dp[1][j-1];
        for(int i=1;i<=n;i++)//先统计 i>=k 的情况
        {
            mx=max(dp[i][j-1],mx)+a[i][j];//用一个变量不断累加，遇到更优的情况就更新之
            dp[i][j]=max(dp[i][j],mx);
        }
        mx=dp[n][j-1];
        for(int i=n;i>=1;i--)//再统计 i<=k 的情况
        {
            mx=max(dp[i][j-1],mx)+a[i][j];//同上
            dp[i][j]=max(dp[i][j],mx);
        }
    }
    printf("%lld",dp[n][m]);
    return 0;
}

DP 不是我最擅长的东西准确来说是我最不擅长的东西，所以考试时并没有做对这道题，只得了 30pts，不过还好前三题都对了，应该是有 1= 了。

TG

这次的提高真的是让我感觉心态爆炸，尤其是 T1T2，T1 就不用说了，恶心大模拟，数据也难算，调试也很**，整体来说很没有体验，T2 犯了一个超级 sb 的错误，导致挂了 35pts，T3T4 还算正常发挥，主要是前两题出错太多，最后只有 150pts，1= 很悬。

T1 儒略日

在开始这道题的题解之前请允许我问候出题人全家。

简单来说，这道题就是让你求从公元前 4713 年 1 月 1 日往后数 rr 天是哪一天，但有几个细节。

  • 从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日这段时间里没有现在百年不闰的说法，只要年份是 44 的倍数就是闰年。
  • 公元 1582 年 10 月 4 日的下一天是公元 1582 年 10 月 15 日。
  • 公元 0 年不存在，即公元前 1 年的下一年是公元 1 年，所以对于公元前年份来说，年份模 44 余 11 的才是闰年。
  • 其他的和现在的历法一样。

一个很简单的方法是用这个天数不停地减去这一年的天数，然后把年份数加一，如果天数小于等于这一年的天数了，就再让它不停的减去这一年的每个月份的天数，直到它小于等于这一月的天数。

然而，CCF 给我们的数据范围是

年份答案不超过 10910^9

况且还有多组数据，所以很明显这个方法行不通，考虑优化。

相信大家都做过这道题，它的思路是用取模来代替周期性的模拟，我们也可以依葫芦画瓢。

具体来说，我们分三段来考虑。

  • 公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日，这一段四年一闰，即四年一个周期。
  • 公元 1582 年 10 月 15 日到公元 1582 年 12 月 31 日，这一段由于不是整年份，又有间隔的天数，所以我们分开特判。
  • 公元 1583 年 1 月 1 日到公元 inf 年 12 月 31 日以后，这一段四年一闰，百年不闰，四百年再闰，即每四百年为一个周期。

具体的就不详细说了，也没什么好说的了，还是看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q,n,mon[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
ll check_year_special(ll x)//带 _special 的就是用来判断 1582 年以前的年份或月份的
{
    if(x<0)
        if((-x)%4==1)
            return 366;
        else
            return 365;
    else
        if(x%4==0)
            return 366;
        else
            return 365;
}
ll check_month_special(ll x,ll y)
{
    if(check_year_special(x)==366&&y==2)
        return 29;
    else
        return mon[y];
}
ll check_year(ll x)
{
    if(x%400==0||(x%4==0&&x%100!=0))
        return 366;
    else
        return 365;
}
ll check_month(ll x,ll y)
{
    if(check_year(x)==366&&y==2)
        return 29;
    else
        return mon[y];
}
int main()
{
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%lld",&n);
        if(n<=2299160)//从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日的天数
        {
            ll y=n/1461*4-4713,m=1,flag=0;//1461 为四年的天数
            n%=1461;
            if(y>=0)
            {
                flag=1;//特判是否过了公元前 1 年
                y++;
            }
            while(n>=check_year_special(y))//一年一年地减
            {
                n-=check_year_special(y++);
                if(y==0)
                {
                    flag=1;
                    y++;
                }
            }
            while(n>=check_month_special(y,m))//一月一月地减
                n-=check_month_special(y,m++);
            if(flag)
                printf("%lld %lld %lld\n",n+1,m,y);
            else
                printf("%lld %lld %lld BC\n",n+1,m,-y);
        }
        if(2299160<n)
        {
            n-=2299161;//减去之前的天数，重新开始计算
            if(n<=16)//特判 1582 年 10 月 15 日到 1582 年 12 月 31 日
                printf("%lld 10 1582\n",n+15);
            if(16<n&&n<=46)
                printf("%lld 11 1582\n",n-16);
            if(46<n&&n<=77)
                printf("%lld 12 1582\n",n-46);
            if(77<n)
            {
                n-=78;
                ll y=1583+n/146097*400,m=1;//146097 为每四百年的天数
                n%=146097;
                while(n>=check_year(y))
                    n-=check_year(y++);
                while(n>=check_month(y,m))
                    n-=check_month(y,m++);
                printf("%lld %lld %lld\n",n+1,m,y);
            }
        }
    }
    return 0;
}

没什么复杂的算法，但需要非常注意细节，同时数学也要好计算器也要用的好，否则是真的难调，我在考场上调了一个半小时都没整对，最后还是爆零。。。

T2 动物园

这道题个人感觉比 T1 简单多了，不过位运算的特性是真的难受，两三处小小的错误直接就丢了 35pts，真的难受。。。

对于这道题，我们可以先根据饲养的动物和要求算出清单，再根据清单反过来算一遍这些动物编号的哪些二进制位可以为 11，假设有 xx 位可以为 11，那就一共可以饲养 2x2^x 种动物，因为我们可以把中间不能为 11 的那些位扣掉，剩下来的就是一个每一位都为 11 的共有 xx 位的二进制数，其中每一位都可以为 00 或者为 11，所以总的方案数就是 2x2^x，再从其中扣掉已经饲养的 nn 种动物，就是还能饲养的动物数。

另外，这道题有很多注意点，下面列举一下（可能不全，欢迎补充）。

  • 这道题 k≤64k\le 64，超出了 long long 的范围，必须要用 unsigned long long，如果你不会拼 unsigned，请找你的英语老师。（40pts）

  • 由于位运算的神奇特性，1<<x会被默认为 int 类型，即如果 xx 大于等于 3131，即使你是将这个值赋给一个 unsigned long long 类型的值，它还是会在运算时自然溢出，解决方法是使用1ull<<x。（40pts）（这就是我在考试时犯的傻逼错误，少打了两个 ull）

  • 根据数据范围，xx 有可能为 6464，如果 nn 此时为 00，那么答案就是 2642^{64}，超出了 unsigned long long 的范围，需要特判，另外，虽然 CCF 的数据没有卡，但个人认为最好是特判一下 x=64x=64 的情况，毕竟这样虽然最后会减一个 nn，但在运算过程中也会溢出。（5pts）

  • 如果你用的是 scanf（用 cin 貌似会超时？），记住 unsigned long long 的格式控制符是 %ull，不是 %llu（没有这种格式控制符），也不是 %uld（也没有这种格式控制符）。（100pts）

我很好奇有多少人挂在了第 44 点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
typedef unsigned long long ll;//unsigned！！！
const ll N=1e6+10;
ll cnt(ll x)
{
    ll sum=0;
    for(;x;x-=lowbit(x))
        sum++;
    return sum;
}
ll n,m,c,k,mk,ans,a[N],p[N],q[N];
bitset<100000010> lt;//我用的 bitset 存清单QwQ
int main()
{
    scanf("%llu%llu%llu%llu",&n,&m,&c,&k);
    for(ll i=1;i<=n;i++)
    {
        scanf("%llu",&a[i]);
        mk|=a[i];
    }
    for(ll i=1;i<=m;i++)
    {
        scanf("%llu%llu",&p[i],&q[i]);
        if(mk&(1ull<<p[i]))
            lt[q[i]]=1;
    }
    for(ll i=1;i<=m;i++)
        if(!lt[q[i]]&&!(ans&(1ull<<p[i])))
            ans^=(1ull<<p[i]);
    ll tot=k-cnt(ans);
    if(tot==64)
        if(n==0)
            printf("18446744073709551616");//特判
        else
            printf("%llu",18446744073709551616-n);//特判*2
    else
        printf("%llu",(1ull<<tot)-n);
    return 0;
}

T3 函数调用

这道题乍一看很像数据结构题，但实际上并不是，而是一道有点思维难度的拓扑排序。

可以发现，这道题实质上可以看成是把所有数乘上一个值 xx，然后再把某些数加上一些值（好好理解一下），举个例子，(a+3)∗4=a∗4+12(a+3)*4=a*4+12。但这样暴力模拟的话肯定会超时（事实上由于 CCF 的数据十分之水，所以暴力可以拿到 70pts）。

考虑计算每个函数的贡献，可以发现，xx 是非常容易求出来的，我们只需要根据函数之间的调用关系，一边 DFS，一边累计所有 22 号函数所乘的值就行了，然后我们需要想办法快速算出那些需要加上的值。因为每一个 11 号函数都是单点增加，所以比较容易想到的办法是求出每一个 11 号函数执行的次数，最后统一增加，这个执行次数不单单指它被调用的次数，还要把它每次被调用之后乘的值也累加进去，比如如果一个 33 号函数的作用相当于先把第一个数加上 33，再把所有数乘上 44，那么第一个被调用的函数就相当于调用了 44 次，这个也是我们需要计算的。

先假设只有一个 33 号函数，它的作用如下：

  1. 把第一个数加 11。
  2. 把所有数乘上 22。
  3. 把第三个数加上 22。
  4. 把第四个数加上 100100。
  5. 把所有数乘上 1010。

那么不难看出，我们相当于是把 55 执行了 11 遍，22，33 和 44 执行了 1010 遍，11 执行了 2020 遍，也就是说，我们可以从后往前遍历每一个 33 号函数，用一个临时变量 tt 累计乘了多少，每调用一个函数，就把它的执行次数加上 tt，并让 tt 乘上这个函数所要乘的数（如果没有要乘的数就默认为 11），慢慢累加就行了。

但这只是一个 33 号函数的情况，实际上整个函数调用过程可能会很复杂，这时候我们又该怎么办呢？

由于题面中说了，不会出现递归，也就是说如果我们把函数调用的过程画成一张图，它实际上是一个 DAG，比如样例二画成一张图的话就是下面这个样子。

因此，我们可以考虑进行拓扑排序，在一开始输入时，对于每一个 33 号函数，把它们抽象成图中的一个点，向它们所调用的那些函数连一条有向边，然后预处理出每个函数所要乘的值 mulimul_i（包括它调用的那些函数，如上图中的 33 乘的数就是 5,6,7,85,6,7,8 所要乘的数的积），可以跑一遍 DFS 解决。在排序过程中，我们不停地累加某个函数的执行次数，对于每一个被函数 ii 调用的函数 jj，它所增加的执行次数为 fi×tf_i\times t（fif_i 是函数 ii 被调用的次数，tt 就是上面提到的那个临时变量），然后再把 tt 乘上 muljmul_j，需要注意，正如上文所说，这个过程必须反向遍历所有边，也就是说，如果一开始的调用顺序为 4 3 5 2 34\ 3\ 5\ 2\ 3，那么遍历顺序就为 3 2 5 3 43\ 2\ 5\ 3\ 4。

对了，有一个技巧，可以把最后的那个执行序列也看成是一个 33 号函数，作为 00 号点建边，DFS 的时候直接从 00 开始就行了。

然后就没什么了，记得不停地取模就行了，还有什么不明白的就看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=998244353;
ll n,m,q,mul[N],vis[N],a[N],in[N],f[N],fun[N][2];
vector<int> edge[N];
ll dfs(int u)
{
    if(vis[u])
        return mul[u];
    vis[u]=1;
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i];
        mul[u]=mul[u]*dfs(v)%mod;
    }
    return mul[u];
}
void topo()
{
    queue<int> q;
    for(int i=0;i<=m;i++)
        if(!in[i])
            q.push(i);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        ll rec=1;
        for(int i=edge[u].size()-1;i>=0;i--)
        {
            int v=edge[u][i];
            f[v]=(f[v]+f[u]*rec%mod)%mod;
            rec=rec*mul[v]%mod;
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    {
        mul[i]=1;
        ll op,p,v,c;
        int g;
        scanf("%lld",&op);
        if(op==1)
            scanf("%lld%lld",&fun[i][0],&fun[i][1]);
        if(op==2)
            scanf("%lld",&mul[i]);
        if(op==3)
        {
            scanf("%lld",&c);
            for(int j=1;j<=c;j++)
            {
                scanf("%d",&g);
                edge[i].push_back(g);
                in[g]++;
            }
        }
    }
    scanf("%lld",&q);
    for(int i=1;i<=q;i++)
    {
        int func;
        scanf("%d",&func);
        edge[0].push_back(func);
        in[func]++;
    }
    f[0]=mul[0]=1;
    dfs(0);
    topo();
    for(int i=1;i<=n;i++)
        a[i]=a[i]*mul[0]%mod;
    for(int i=1;i<=m;i++)
        if(fun[i][0])
            a[fun[i][0]]=(a[fun[i][0]]+f[i]*fun[i][1]%mod)%mod;
    for(int i=1;i<=n;i++)
        printf("%lld ",a[i]);
    return 0;
}

T4 贪吃蛇

不会做。。。

总结

啊，总算写完了，这篇文章前前后后大概也咕了几周时间，个人觉得写得还可以，只有函数调用写的稍微差点，可能没有讲得很清楚，实在不懂就去参考一下 lg 上的题解吧，那些大佬比我写的好多了。

该说的开头也说了，这次的题其实真心没有什么很难的算法或是数据结构，但确实很考人的思维和码力，而我的 tg 分数不高，主要就是 T1 和 T2 丢分太多（T1 爆零了。。。），这也看出来我还是不够仔细，而且心态也不够好，一到考试脑子就不清醒（难道是没有睡午觉的原因？），以后还是应当多锻炼锻炼。

最后，希望我 NOIP2020 能考个稍微好点的分数，加油！