CSP-S模擬37
T1: gcd&xor (gcdxor)
思路：
算錯復雜度導致結束前 \(3 ~ min\) 臨時加了個快讀，差點把文件 \(IO\) 整錯了，嚇死個人...
首先，暴力大家肯定都會。
遇事不決暴力打表找規律。所以啥原理根本不懂，只能說是由表可得。
其實我覺得再從頭打表找一遍規律意義不大，就不展開了。
代碼：
$code1$
#include<iostream>
using namespace std;
int n,ans;
inline int gcd(int x,int y){
if(!y) return x;
return gcd(y,x%y);
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=2;i<=n;i+=2){
for(int j=n/(i+1);j>=1;j--){
if(gcd(i*j,(i+1)*j)==((i*j)^((i+1)*j))) ans++;
}
}
cout<<ans<<'\n';
return 0;
}
$code2$
#include<iostream>
#define re register
using namespace std;
int n,sum,maxn;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
inline void write(int x){if(x<0)x*=-1,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');return;}
int main(){
// freopen("gcdxor.in","r",stdin);
// freopen("gcdxor.out","w",stdout);
n=read();
sum=(n-1)>>1;
maxn=(n+2)/3;
for(re int i=2;i<=maxn;i++){//枚舉i,j的差值，即為gcd
for(re int j=2;j<n/i;j++){//最大能是多少倍
if(((j*i)^((j+1)*i))==i){
sum++;
}
}
}
write(sum);
return 0;
}
T2：異或樹 (xortree)
思路：
顯然無論如何進行操作 \(1\)，非葉子結點都不會產生影響（廢話，都不擴展非葉子結點 【記得讀題哦】）。
所以我們可以分開統計葉子節點的貢獻和非葉子結點的貢獻，最后的答案加起來就好了。
我們設 \(f_i\) 表示權值為 \(i\) 的葉子節點的個數（其實就是葉子節點的子樹異或和）， \(g_i\) 表示子樹異或和為 \(i\) 的非葉子結點個數。
轉移就很顯然啦。
每個節點都可以跟它的左子節點抵消掉，所以新生成的子樹的異或和為它的右子節點的權值。
而每個節點跟它的左子節點相等，所以新增的葉子結點即為原葉子結點的新增右子節點。
我們假設一個葉子節點的權值為 \(t\) ，則
然后對著敲就好啦~~
代碼：
$code$
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=8888,mod=998244353,maxn=1<<13;
int k,q,op,x,f[N],g[N],h[N];
signed main(){
// freopen("xortree.in","r",stdin);
// freopen("xortree.out","w",stdout);
ios::sync_with_stdio(false);
cin>>k>>q;
f[k]=1;
while(q--){
cin>>op>>x;
if(op==1){
memcpy(h,f,sizeof(f));
for(int i=0;i<=maxn;i++){
g[i]=(g[i]+h[i^x])%mod;
f[i]=(f[i]+h[i^x])%mod;
}
}else cout<<(f[x]+g[x])%mod<<'\n';
}
return 0;
}
T3：符文石 (stone)
思路：
你當然可以效法某人用dfs硬創過去，好像還挺優？
首先，根據當代年輕人 \(200 ~ \%\) 的反骨，我們就要跟題目反著建邊（嘿嘿，其實是反著建邊便于操作）
由于正著建邊所得到的點集為它所能到的點的集合，那反著建邊就是能到它的點的集合咯。那我們就可以給它 \(topo\) 一下，然后再把集合合并一下就好啦。
那如何合并呢？
由于兩個數按位與以后的結果一定小于等于這兩個數中較小的一個，假設我們當前維護到的按位與的最大值為 \(maxn\) ，那么以后對答案產生貢獻的的數一定大于等于 \(maxn\) ，而等于 \(maxn\) 的數最多保留兩個。
綜上，我們只需要兩兩合并集合的時候把集合中大于當前最大按位與的值的數和至多兩個等于當前最大按位與的值的數存下來就好。
\(Last...\) 這次不能 #define int long long了，不然可能會爆空間的哇
代碼：
$code$
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
const int N=5e5+5;
int m,n,u,v,cnt,du[N],head[N];bool vis[N];
ll a[N];
struct node{int to,nxt;}e[N<<1];
struct flower{
int cnt,id[65];
ll maxn,val[65];
}p[N];
queue<int> q;
inline void add(int x,int y){
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
inline void merge(flower &x,flower y){
flower res;
res.maxn=max(x.maxn,y.maxn);
res.cnt=0;
for(int i=1;i<=x.cnt;i++){
for(int j=1;j<=y.cnt;j++){
if(x.id[i]!=y.id[j]) res.maxn=max(res.maxn,x.val[i]&y.val[j]);
}
}
bool flag=0;
for(int i=1;i<=x.cnt;i++){
if(!vis[x.id[i]]){
if(x.val[i]>res.maxn){
res.id[++res.cnt]=x.id[i];
res.val[res.cnt]=x.val[i];
vis[x.id[i]]=1;
}else if(x.val[i]==res.maxn&&!flag){
flag=1;
res.id[++res.cnt]=x.id[i];
res.val[res.cnt]=x.val[i];
vis[x.id[i]]=1;
}
}
}
for(int i=1;i<=y.cnt;i++){
if(!vis[y.id[i]]){
if(y.val[i]>res.maxn){
res.id[++res.cnt]=y.id[i];
res.val[res.cnt]=y.val[i];
vis[y.id[i]]=1;
}else if(y.val[i]==res.maxn&&!flag){
flag=1;
res.id[++res.cnt]=y.id[i];
res.val[res.cnt]=y.val[i];
vis[y.id[i]]=1;
}
}
}
for (int i=1;i<=x.cnt;i++) vis[x.id[i]]=0;
for (int i=1;i<=y.cnt;i++) vis[y.id[i]]=0;
x=res;
}
signed main(){
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--){
cin>>u>>v;
add(v,u);
du[u]++;
}
for(int i=1;i<=n;i++){
p[i].cnt=1;
p[i].maxn=-1;
p[i].id[1]=i;
p[i].val[1]=a[i];
}
for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
merge(p[y],p[x]);
du[y]--;
if(!du[y]) q.push(y);
}
}
for(int i=1;i<=n;i++) cout<<p[i].maxn<<' ';
return 0;
}
后言
閑話
為何說未來迷茫？
紅星在遠處照耀 ，共黨在前方領導
為何說無路可走？
社會主義建設的道路就在腳下
為何說身后無人？
智慧的老祖宗，強大的祖國，十四萬萬的同胞都在你的身后
歌詞
那一年你和我一樣年紀
年輕得像首青澀的歌曲
但為了創造夢中那個新天地
你轉身 匆匆走進風雨
我看見千萬個可愛的你
不回頭向硝煙深處奔去
多少個青春背影消失在夜里
換來晨曦
我仰望你看過的星空
穿過百年時空再相逢
你轉過身之前的那個笑容
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風中搖曳的那抹紅
在心中 心中
舉起手我說出同樣誓言
黑白間你的笑容多清晰
你說你從來也不后悔把一生
奉獻給 這片遼闊大地
我多想伸手緊緊擁抱你
告訴你一切都塵埃落定
百年前你夢想的那個新中國
有多美麗
我仰望你看過的星空
穿過百年時空再相逢
在此刻我們總會心靈相通
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風中搖曳的那抹紅
在心中 心中
我仰望你看過的星空
穿過百年時空再相逢
在此刻我們總會心靈相通
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風中搖曳的那抹紅
在心中 心中
