【解题报告】CSP-S2020
【解题报告】CSP-S2020
从这一年开始NOIP和CSP正式变为四道题目，两天的考试已经成为历史了
T1 儒略日
思路
当年这道题目把我恶心死了，导致我没办法去NOIP2020
这道题目按理来说就是模拟，中间要处理一下格里高利历的空出的日期，以及公元前和公元后的一些闰年的处理，还有一些月份的处理
时至今日，我还是不想打模拟题
于是暗示了我的完美结局
实际上我们可以预处理四百年的信息，再来根据这个信息稍微改变以及推算一下就好了
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int maxn=146097;
int q;
int y[maxn],m[maxn],d[maxn];
int r,tmp;
int calc(int year,int month)
{
if(month==2)
{
if(year%4!=0) return 28;
else
{
if(year%100!=0) return 29;
else
{
if(year%400!=0) return 28;
else return 29;
}
}
}
if(month==4||month==6||month==9||month==11)
return 30;
else return 31;
}
signed main()
{
m[0]=d[0]=1;
for(int i=1;icalc(y[i],m[i]))
{
m[i]++,d[i]=1;
}
if(m[i]>12)
{
y[i]++;
m[i]=1;
}
}
cin>>q;
while(q--)
{
cin>>r;
if(r>2299160)
{
r-=2159351;
tmp=r/maxn*400+1200;
r%=maxn;
}
else
{
tmp=r/1461*4-4712;
r%=1461;
}
cout<0)
cout< T2 动物园
思路
位运算
甚至比T1还要简单
我们直接用一个 unsigned long long 来储存所有的饲料要求
然后对于所有的剩下的没有选的动物的编号跟要求进行对比
然后我们对于每个要求，进行一次操作
我们继续观察发现，既然每个动物都有的话，我们实际上要知道的就是饲料清单上第 \(p_i\) 位上为 \(0\)? 的数目
实际上答案就是 \(2^{k-S}-n\)?
注意 \(2^{64}\) 需要特判一下
#include
#include
#include
#include
#include
#define int unsigned long long
using namespace std;
int n,m,c,k;
int ans,dw,ls;
signed main()
{
cin>>n>>m>>c>>k;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
dw|=x;
}
for(int i=1;i<=m;i++)
{
int p,q;
cin>>p>>q;
ls|=1ull<>i)&1)||((dw>>i)&1))
ans++;
if(ans==64&&n==0)
cout<<"18446744073709551616"<<'\n';//特判
else
{
if(ans==64)
cout<<-n<<'\n';
else
cout<<(1ull< T3 函数调用
思路
当时考场上以为很简单，打了这个，结果空间爆了
所以我们进行一波看
我们可以先处理乘法，然后对于每次加法再弄一个乘法操作，相当于打一个懒惰标记
然后我们再次了解发现，函数的调用关系实际上就是一个拓扑序
我们做两次拓扑排序，一次处理函数执行一次后乘的倍数
另一次处理函数等价于执行多少次
因为乘法执行一次，等于加法执行若干次
这样就做出来了
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const int mod=998244353;
int n,m,q;
int cnt[maxn];
int a[maxn];
int type[maxn],mul[maxn],add[maxn],pos[maxn];
int out1[maxn],out2[maxn];
vector g1[maxn],g2[maxn];
void topo1()
{
queue q;
for(int i=0;i<=m;i++)
{
out1[i]=g2[i].size();
if(out1[i]==0)
q.push(i);
}
while(q.size())
{
int x=q.front();
q.pop();
for(int i=0;i q;
for(int i=0;i<=m;i++)
{
out2[i]=g1[i].size();
if(out2[i]==0)
q.push(i);
}
while(q.size())
{
int x=q.front();
int tag=1;
q.pop();
for(int i=g2[x].size();i>0;--i)
{
int e=g2[x][i-1];
cnt[e]=(cnt[e]+1ll*cnt[x]*tag)%mod;
tag=1ll*tag*mul[e]%mod;
out2[e]--;
if(out2[e]==0)
q.push(e);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>m;
mul[0]=1;
for(int i=1;i<=m;i++)
{
cin>>type[i];
if(type[i]==1)
{
mul[i]=1;
cin>>pos[i]>>add[i];
}
if(type[i]==2)
cin>>mul[i];
if(type[i]==3)
{
mul[i]=1;
int c;
cin>>c;
for(int j=0;j>e;
g1[e].push_back(i);
g2[i].push_back(e);
}
}
}
cin>>q;
cnt[0]=1;
while(q--)
{
int x;
cin>>x;
g1[x].push_back(0);
g2[0].push_back(x);
}
topo1();
topo2();
for(int i=1;i<=n;i++)
a[i]=1ll*a[i]*mul[0]%mod;
for(int i=1;i<=m;i++)
{
if(type[i]==1)
a[pos[i]]=(a[pos[i]]+1ll*cnt[i]*add[i])%mod;
}
for(int i=1;i<=n;i++)
cout< T4 贪吃蛇
思路
贪心
有一个结论，如果当前最强的蛇吃掉的最蒻的蛇之后，没有变成最蒻的蛇，那么他一定会继续吃
现在考虑最强的蛇，如果吃掉一条蛇之后，他还是最强的蛇的话，肯定会吃
如果吃掉一条蛇之后最强的蛇不是他了，这个时候，新的最强的蛇没有刚才强，现在最蒻的蛇也没有刚才蒻，第二强的蛇吃掉了最蒻的蛇之后一定没有第一次最强的更强，所以会死在第一次最强的前面，所以如果这个蛇能想办法不死的话，那么第一次最强的蛇也一定不会死
如果吃完蛇之后会变成最蒻的蛇，吃不吃呢？
如果吃的话，我们第二次最强的蛇如果吃掉了第一次最强的蛇
如果不是最蒻的蛇的话，那么第二次最强的蛇一定会吃掉第一次最强的蛇，那么第一次最强的蛇则不会选择吃最蒻的蛇
同理，如果第二次最强的蛇吃掉最蒻的蛇之后变成了最蒻的蛇，我们按照刚才相同的思路考虑第三条蛇吃不吃，依次考虑下去，子子孙孙无穷匮也
所以我们只用模拟一下两个阶段
第一个阶段是，所有最强的蛇进食之后肯定不是最强的蛇，所以我们直接吃最蒻的蛇
第二个阶段是，所有最强的蛇进食之后都是最蒻的蛇，直到有一条蛇可以放心大胆吃
阶段一结束的时候，游戏就基本完了
我们可以用双端队列来维护蛇
因为用双端队列是有序进来的，所以具有单调性
对于第一个阶段和第二个阶段，我们这么模拟
第一个阶段：
我们每次从 \(q_1,q_2\) 的尾部取出最强的蛇，从 \(q_1\) 的头部取出最蒻的蛇，如果吃完了之后是最蒻的，那就进入第二阶段，否则装进 \(q_2\) 的头部，继续上述过程
第二个阶段：
此时最蒻的蛇没必要在入队了，我们一直进食，知道总共的蛇的数量等于 \(2\) 或者进食之后不是最蒻的为止，我们找最强的蛇依然是从 \(q_1,q_2\) 的队尾找
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000005;
const int inf=1e9;
int T,n,a[maxn];
pair q1[maxn],q2[maxn];
int l1,r1,l2,r2;
pair get_max()//取最大蛇
{
if(r1==l1)
return q2[l2++];
else if(r2==l2)
return q1[--r1];
else if(q2[l2]>q1[r1-1])
return q2[l2++];
else return q1[--r1];
}
pair get_min()//取最小
{
if(l1==r1)
return q2[--r2];
else if(r2==l2)
return q1[l1++];
else if(q2[r2-1] Min(pair x,pair y)
{
return x x=get_min(),y=get_max();
pair z=Min((l1z||cnt==n-1)
{
if(flag)
{
cout<>T;
T--;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
solve();
while(T--)
{
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
cin>>a[x];
}
solve();
}
return 0;
}