NOIP2023模拟12联测33
构造
手摸你就会发现 \(ryxyryxyr\)，这样会更优，而且从第三行开始会有多余的贡献。
点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
char s[100];
char ans[100][100];
int main(){
freopen("ryx.in","r",stdin);
freopen("ryx.out","w",stdout);
int n;
scanf("%d",&n);
if(n<=20){
if(n==0){
cout<<1<<" "<<3<<endl;
for(int i=1;i<=3;i++){
cout<<"x";
}
return 0;
}
int x=n*2,y=3;
printf("%d %d\n",x,y);
for(int i=1;i<=n*2;i++){
if(i%2) printf("ryx\n");
else printf("xxx\n");
}
return 0;
}
s[1]='r';
int tot=1;
for(int i=1;i<=9;i++){
s[++tot]='y';s[++tot]='x';
s[++tot]='y';s[++tot]='r';
}
s[++tot]='y';s[++tot]='x';
if(n<=100){
int x=40,y=39;
printf("%d %d\n",x,y);
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
ans[i][j]='x';
}
}
int sum=n;
for(int i=1;i<=x;i++){
if(sum<=19){
i++;
for(int j=1;j<=tot;j++){
if(sum){
ans[i][j]=s[j];
if(j>=3){
if(s[j]!=s[j-1] && s[j-1]!=s[j-2] && s[j]!=s[j-2]) sum--;
}
}
}
break;
}
if(!sum){
continue;
}
if(i%2){
for(int j=1;j<=tot;j++) ans[i][j]=s[j];
sum-=19;
}
else{
continue;
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cout<<ans[i][j];
}
cout<<endl;
}
return 0;
}
int sum=n;
int x=40,y=40;
cout<<x<<" "<<y<<endl;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
ans[i][j]='y';
}
}
for(int i=1;i<=x;i++){
if(i==1 || i==2){
for(int j=1;j<=tot;j++) ans[i][j]=s[j];
sum-=19;
continue;
}
if(sum>=(19+38)){
for(int j=1;j<=tot;j++) ans[i][j]=s[j];
sum-=(19+38);
continue;
}
else{
if(sum){
sum--;
ans[i][1]=s[1];
}
for(int j=2;j<=tot;j++){
if(j%2==0) ans[i][j]='y';
else{
if(sum>=3){
sum-=3;
ans[i][j]=s[j];
}
else{
break;
}
}
}
break;
}
}
if(sum){
ans[1][y]=s[1],ans[2][y]=s[2];
for(int i=3;i<=x;i++){
if(!sum) break;
ans[i][y]=s[i];
if(sum){
if(s[i]!=s[i-1] && s[i]!=s[i-2] && s[i-1]!=s[i-2]){
sum--;
}
}
}
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cout<<ans[i][j];
}
cout<<endl;
}
}
游戏
手摸一场了考试样例没摸出来。不太擅长策略题。
从大到小排完序后，同学最优肯定是将概率分配给一个前缀，老师也是，我们可以二分一个 \(mid\) 表示学生能否使得被抓人数 \(\leq mid\)。
此时对于小于 \(mid\) 的 \(a_i\) 不需要考虑，对于大于等于的有 \((1-p)*a_i\) 的期望抓到人数，让 \((1-p)*a_i /leq mid\) 就可以求出下界，将下界加起来，如果大于 1 ，那就不合法，反之成立。
还可以考虑因为选的是一个前缀，且概率和为 1，\(m\) 为选的个数，所以
\[(1-p_i) \times a_i \leq ans \]\[p_i \geq \frac{a_i-ans}{a_i} \]\[\sum_{i=1}^{i=m} \frac{a_i-ans}{a_i} =1 \]化简的到 \(ans=\frac{m-1}{\sum_{i=1}^{i=m} \frac{1}{a_i}}\)
对每个前缀求出 \(ans\) 去 \(\min\) 就可以。
数数
考虑在序列上一个一个加数，使其构成单调递减的序列 \(F\)，合法，考虑可以转移到的状态。
首先一开始是一个长度为 \(n\) 的空序列，然后你从小到大加入每一个数，有一些限制，假设你加入的数在 \(F\) 中出现过，且出现区间为 \(L,R\)。那么考虑将这个数 \(x\) 加入到一个空序列上，限制肯定是这个序列长度 \(len = R\)，小于 \(R\) 的话，个数不满足，大于 \(k\) 的话，F值就会大于 \(x\)。然后这个空序列会变成两个序列，然后考虑剩下的空序列最长 \(len' == L-1\)，因为跟上面一样，考虑只存长度，这样状态数只有不到 \(2.4 \times 10^5\) 个，然后转移。
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int mod=998244353;
using namespace std;
const int N=100;
int f[N],n;
int l[N],r[N];
map<vector<int>,int>mp;
queue<vector<int>> q;
vector<int> s,b;
map<vector<int>,bool> vis;
signed main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) l[i]=n+1,r[i]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&f[i]);
l[f[i]]=min(l[f[i]],i),r[f[i]]=max(r[f[i]],i);
}
s.push_back(n);
mp[s]=1;
q.push(s);
vis[s]=1;
while(!q.empty()){
s=q.front();
q.pop();
vis[s]=0;
int siz=s.size();
int i=siz;
int len=0;
for(int j=0;j<siz;j++) len=max(len,s[j]);
int sum=0;
int cnt=0;
for(int j=0;j<siz;j++){
if(s[j]==len) sum++;
if(s[j]==r[i]) cnt++;
}
if(l[i]==n+1 || r[i]==0){
for(int j=0;j<siz;j++){
if((s[j]<len || sum>1) && s[j]>0){
for(int k=1;k<=s[j];k++){
b.clear();
b=s;
b.erase(b.begin()+j);
b.push_back(k-1);
b.push_back(s[j]-k);
sort(b.begin(),b.end());
if(!vis[b]){
vis[b]=1;
q.push(b);
}
mp[b]=(mp[b]+mp[s])%mod;
}
}
}
}
else{
if(len!=r[i]) continue;
for(int j=0;j<siz;j++){
for(int k=1;k<=s[j];k++){
b.clear();
b=s;
b.erase(b.begin()+j);
b.push_back(k-1);
b.push_back(s[j]-k);
sort(b.begin(),b.end());
if(b[b.size()-1]==l[i]-1){
if(!vis[b]){
vis[b]=1;
q.push(b);
}
mp[b]=(mp[b]+mp[s])%mod;
}
}
}
}
}
vector<int> ed;
ed.clear();
for(int i=1;i<=n+1;i++){
ed.push_back(0);
}
printf("%lld",mp[ed]);
}
滈葕
首先考虑 \(D,C\)，因为这个限制少，所以尽可能选会更优，选之前判一下哪些点不可以选 \(D或C\)。然后选 \(A,B\)，这个可以染色，如果边权为 \(1\) 则颜色不同，否则相同，然后判无解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
const int M=1e5+10;
int head[M],ver[N*2],nex[N*2],edge[N*2],tot=0;
void add(int x,int y,int w){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=w;
}
int flatd[M],flatc[M];
struct asd{
int x,y,w;
}a[N];
int ans[M],getans=0;
bool vis[N],flat[N];
int dfs1(int x,int f){
flat[x]=1;
if(flatc[x]) return flatc[x];
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==f) continue;
if(flat[y]){
if(flatc[y]==1){
flatc[x]=1;
return 1;
}
continue;
}
if(dfs1(y,x)==1){
flatc[x]=1;
return 1;
}
}
flatc[x]=2;
return 0;
}
int dfs2(int x,int f){
flat[x]=1;
if(flatd[x]) return flatd[x];
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==f) continue;
if(flat[y]){
if(flatd[y]==1){
flatd[x]=1;
return 1;
}
continue;
}
if(dfs2(y,x)==1){
flatd[x]=1;
return 1;
}
}
flatd[x]=2;
return 0;
}
void dfs(int x,int f){
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==f) continue;
if(ans[y]){
if(edge[i]) if(ans[x]==ans[y]) getans=1;
if(!edge[i]) if(ans[x]!=ans[y]) getans=1;
continue;
}
if(edge[i]==1){
if(ans[x]==1) ans[y]=2;
else ans[y]=1;
}
else{
ans[y]=ans[x];
}
dfs(y,x);
}
}
int main(){
freopen("dopetobly.in","r",stdin);
freopen("dopetobly.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
if(a[i].w){
flatd[a[i].x]=1;
flatc[a[i].y]=1;
}
}
for(int i=1;i<=m;i++){
if(a[i].w==0){
vis[a[i].x]=vis[a[i].y]=1;
add(a[i].x,a[i].y,a[i].w);
}
}
for(int i=1;i<=n;i++){
if(!flatc[i]){
dfs1(i,0);
}
}
tot=0;
memset(head,0,sizeof(head));
memset(flat,0,sizeof(flat));
for(int i=1;i<=m;i++){
if(a[i].w==0){
add(a[i].y,a[i].x,a[i].w);
}
}
for(int i=1;i<=n;i++){
if(!flatd[i]){
dfs2(i,0);
}
}
for(int i=1;i<=n;i++){
if(flatd[i]==2) ans[i]=4;
if(flatc[i]==2) ans[i]=3;
}
tot=0;
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++){
if(!ans[a[i].x] && !ans[a[i].y]){
add(a[i].x,a[i].y,a[i].w);
add(a[i].y,a[i].x,a[i].w);
}
}
for(int i=1;i<=n;i++){
if(!ans[i]){
ans[i]=2;
dfs(i,0);
}
}
if(getans){
printf("NO");
return 0;
}
if(!getans) printf("YES\n");
for(int i=1;i<=n;i++){
if(ans[i]==1) printf("A");
if(ans[i]==2) printf("B");
if(ans[i]==3) printf("C");
if(ans[i]==4) printf("D");
}
}
NOIP2023模拟13联测34
origen
首先对 \(a_i\) 做前缀异或和，记为 \(s_i\)。
然后原式变为 \(\sum^{n}_{i=0}\sum_{j=i+1}^{n}(s_i \oplus s_j)^2\)
然后考虑第 \(i\) 位加入 \(s_i\)，之后的答案为 \(ans^2\)，然后 \(ans^2=(2^0 + 2^1 +…+ 2^{25})^2\)，也就是将其二进制拆分，然后按位考虑，肯定有两位异或起来都为 \(1\) 的才会产生贡献，贡献类似于 \(2 \times a \times b \times k_i\)，\(k_i\) 表示贡献的次数，然后对于两位相等的没有系数 \(2\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=2*1e5+10;
int a[N],s[N];
int f[25][3][25][3];
int ans[N];
signed main(){
freopen("origen.in","r",stdin);
freopen("origen.out","w",stdout);
int n;
while(scanf("%lld",&n)==1){
// scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
int cnt=0;
for(int i=1;i<=n;i++){
s[i]=s[i-1]^a[i];
for(int j=1;j<=20;j++){
for(int k=j;k<=20;k++){
int t1=((s[i]&(1ll<<(j-1)))>0);
int t2=((s[i]&(1ll<<(k-1)))>0);
f[j][t1][k][t2]++;
if(j==k){
ans[i]+=(1ll<<(j-1))*(1ll<<(k-1))%mod*f[j][t1^1][k][t2^1]%mod;
ans[i]%=mod;
continue;
}
ans[i]+=2*(1ll<<(j-1))*(1ll<<(k-1))%mod*f[j][t1^1][k][t2^1]%mod;
ans[i]%=mod;
}
}
ans[i]+=s[i]*s[i]%mod;
ans[i]%=mod;
cnt=(cnt+ans[i])%mod;
}
printf("%lld",cnt);
}
}