首页 > 其他分享 >『模拟赛』冲刺CSP联训模拟1

『模拟赛』冲刺CSP联训模拟1

时间:2024-09-25 20:25:32浏览次数:7  
标签:her could 联训 place she still CSP 模拟 know

Rank

我的我要爆了

image

A. 几何

上来思路就假了,不知道,样例全过,本来就算假也能拿点,结果绑包了,妈的。

正解 dp,设 \(f_{i,j,k}\) 表示串 \(s\) 匹配到 \(i\) 位,模式串 \(x\) 拼接至 \(j\) 位,\(y\) 拼接至 \(k\) 位是否可行,滚动数组优化,复杂度 \(\mathcal{O(|s||x||y|)}\),不太能过,位运算优化一下就能过了,不过数据水,把 string 改成 char 然后改掉大量的取模换成三目运算符也能过。

代码是卡过去的,不放了。

B. 分析

树形 dp。

赛时想的找直径假了就不细说了,又因为绑包所以一分没有。

设计状态 \(f_{i,0/1,0/1}\) 表示对于节点 \(i\),其度数为奇(1)偶(0)且其子树(不含该点)内有(1)没有(0)度数为奇的点。

考虑转移,可以将其想象为合并两棵子树。对于任意一条边,我们都可以通过操作 A 添加一条重边,即在二者间连两条边,此时其与其子节点的度数奇偶性不变,转移对象是 \(f_{u,j_u,k_u|j_v|k_v}\),理解就是合并后子树变成了原先的子树和子节点的子树和子节点,它们的奇偶性共同决定了转移的目标。

再考虑不加边的情况,此时我们考虑如何使用操作 B。一个结论:我们需要的 B 操作次数为 \(\frac{度数为奇的点个数}{2}-1\)。我们此时只在两点间连一条边,奇偶性相反,所以额外花费有:

\[zc=\begin{cases} -B\quad j_u\ and\ j_v\\B\quad\ \ \ !j_u\ and\ !j_v\\ 0\quad \ \ \ \ else \end{cases} \]

转移对象同上,只是此时当前节点度数与子节点度数的奇偶性会取反,异或一下就行。

额外的,\(f_{i,1,0}\) 这种情况是不存在的。因为一条边会给一棵子树内带来两次度数的增加,如果当前节点的度数为奇,其子树内一定至少有一个节点度数为奇。当然它对答案没影响,求简便的话按上面写就行,想抢最优解可以考虑减少这种情况然后循环展开去做。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch=getchar();lx x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int,int>
#define fi first
#define se second
const int Ratio=0;
const int N=5e5+5;
const int mod=998244353;
int n,A,B;
int hh[N],to[N<<1],ne[N<<1],cnt;
ll f[N][2][2],g[2][2];
namespace Wisadel
{
    inline void Wadd(int u,int v){to[++cnt]=v,ne[cnt]=hh[u],hh[u]=cnt;}
    inline void Wdfs(int u,int fa)
    {
        f[u][0][0]=0;
        f[u][0][1]=f[u][1][0]=f[u][1][1]=1e18;
        for(register int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(v==fa) continue;
            Wdfs(v,u);
            fo(j,0,1) fo(k,0,1) g[j][k]=f[u][j][k],f[u][j][k]=1e18;
            fo(j1,0,1) fo(j2,0,1) fo(k1,0,1) fo(k2,0,1)
            {
                f[u][j1][j2|k1|k2]=min(f[u][j1][j2|k1|k2],g[j1][j2]+f[v][k1][k2]+A);
                ll zc=(j1&&k1)?-B:(!j1&&!k1)?B:0;
                f[u][j1^1][j2|(k1^1)|k2]=min(f[u][j1^1][j2|(k1^1)|k2],g[j1][j2]+f[v][k1][k2]+zc);
            }
        }
    }
    short main()
    {
        freopen("analyse.in","r",stdin),freopen("analyse.out","w",stdout);
        n=qr,A=qr,B=qr;
        fill(hh+1,hh+1+n,-1);
        fo(i,1,n-1)
        {
            int a=qr,b=qr;
            Wadd(a,b),Wadd(b,a);
        }
        Wdfs(1,0);
        printf("%lld\n",min({f[1][0][0],f[1][1][1]-B,f[1][0][1]-B}));
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 代数

die 数

神秘期望题,不过还是被 5k 等大神琢磨出来了,jijidawang 还给出了第二类斯特林数的 \(\mathcal{O(nk)}\) 做法,膜拜!

D. 组合

有点像小时候表演过的魔术:你内心选好一个 1~100 之内的数,我拿出几张卡片,你需要回答在卡片上有没有你所想的数字,全部问完后就能知道你选的数是什么。其实原理就是选不同的数回答时的组合不同,也就是这道题的简单版,其实魔术中还有能根据第一个数的特殊快速算出答案带来更好节目效果的设置,但跟这道题就没啥关系了。

我们把每次询问的结果设为 \(ans_i\),由上基础思想可知能够根据全部的 \(ans_i\) 可以分析得出选的无序对是多少。根据满分所需 \(m\le 26\),\(ans_i\in[0,1]\),比较好联想到总结果为一个二进制下 26 位数的数,而不同的无序对该数不同。

如果一个数的话就太简单了,有该数为 1 没有为 0,而两个数的话只要询问中有一个有就为 1 否则为 0,发现没有,相当于把数 \(a\) 的结果 \(x_a\) 与数 \(b\) 的结果 \(x_b\) 做了位或操作。

这样题意就得到了进一步转化,我们需要找到 1000 个数使得每个无序对 \((a,b)\) 的 \(x_a|x_b\) 结果不同。搜了一下网上的构造方法,发现都没有给出 std 中某些特定值的来源,唯一有可能实现的是模拟退火,有兴趣可以实现一下。主要思路就是随数,然后加入答案数组,条件为与当前答案数组内任意数的位或值未出现过,可以用 bitset 标记。求出这 1000 个数后就很简单了,从 1 到 26 位询问这 1000 个数每一位上的状态(1/0)。

感觉 std 做法很神奇但探究这种构造方法意义不大,也许都是试错法得出来的。

std 正常码风

1000 个数输出在文件里。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int N=20;
int a[1015];
bitset<1073741824> bk;
int main(){
    int cur=0;
    vector<int> vec;
    for(int i=0;i<(1<<N);i++){
        if(__builtin_popcount(i)==8) vec.pb(i);
    }
    for(int i=0;i<(1<<N);i++){
        if(__builtin_popcount(i)==9) vec.pb(i);
    }
    for(int i=1;i<=1010;i++){
        bool fl2=0;
        for(auto t:vec){
            a[i]=t;
            bool fl=0;
            for(int j=1;j<=i;j++){
                if(bk[a[i]|a[j]]||(i!=j&&i<=996&&__builtin_popcount(a[i]|a[j])<11)){
                    fl=1;
                    for(int k=1;k<j;k++) bk[a[i]|a[k]]=0;
                    break;
                }
                bk[a[i]|a[j]]=1;
            }
            if(fl) continue;
            fl2=1;
            break;
        }
        if(!fl2){
            N++;
            vec.clear();
            for(int j=0;j<(1<<N);j++){
                if(__builtin_popcount(j)==8) vec.pb(j);
            }
            if(N>=24){
                for(int j=0;j<(1<<N);j++){
                    if(__builtin_popcount(j)==9) vec.pb(j);
                }
            }
            if(N==26){
                for(int j=0;j<(1<<N);j++){
                    if(__builtin_popcount(j)!=8&&__builtin_popcount(j)!=9) vec.pb(j);
                }
            }
            i--;
            continue;
        }
        cout<<i<<' '<<N<<endl;
        if(N>26){
            cur=i-1;
            break;
        }
    }
    freopen("122.out","w",stdout);
    for(int i=1;i<=1000;i++) cout<<a[i]<<',';
    cout<<endl;
    return 0;
}

提交答案题,正解代码没意义。


绑包是最似蚂的行为!

还有 ZROI 这么喜欢放树形 dp 题吗,两天了,明天再有就。。。

题目质量确实很高啊,这次打的错解不算暴力,所以相当于没挂(。

欠的越来越多了,希望早日把那个smjb线段树调出来。


完结撒花~

image

Vibe

Wine out on a Wednesday
Glass full 'cause she thirsty
She said don't drink till it's Thursday
But she'll come out on a workday
When all work and no play could just make Jane go crazy
And it's no fun to worry goin' home leaving early
Then she run it up back it up when she know you feelin' the work
Turn it up just a touch givin' love so good that it hurts
Till she f**k it up leanin up even though she still on the up
Leave you shook turn and looks make you never want to leave
'Cause whether Monday Tuesday Wednesday
You know you could still feel her vibe
Or on a Thursday Friday Saturday
You know she could go one more time
And even if they stop the beat or it's time to leave
You know she could go one last time
'Cause whether her place your place
You know some way you could still feel her vibe
You could still you could still
You could still you could still
You could still feel her vibe
You could still you could still
You could still you could still
You could still feel her vibe
And even if they stop the beat or it's time to leave
You know she could go one last time
'Cause whether her place your place
You know some way you could still feel her vibe
She feelin' caught in the waves
The way she movin' her waist
And you're watchin' that body
The rhythm she rockin' no one could complain
There's a certain kind of grace it takes
To dance like nobody's there
No she don't need no one because the song's still on
'Cause whether Monday Tuesday Wednesday
You know you could still feel her vibe
Or on a Thursday Friday Saturday
You know she could go one more time
And even if they stop the beat or it's time to leave
You know she could go one last time
'Cause whether her place your place
You know some way you could still feel her vibe
You could still you could still
You could still you could still
You could still feel her vibe
You could still you could still
You could still you could still
You could still feel her vibe
And even if they stop the beat or it's time to leave
You know she could go one last time
'Cause whether her place your place
You know some way you could still feel her vibe
Monday Tuesday Monday Tuesday
Or on a Thursday Friday Thursday Friday
Even if they stop the beat if they stop the beat
'Cause whether her place your place her place your place
Vibe
You could still you could still
You could still you could still
You could still feel her vibe
You could still you could still
You could still you could still
You could still feel her vibe
And even if they stop the beat or it's time to leave
You know she could go one last time
'Cause whether her place your place
You know some way you could still feel her vibe

标签:her,could,联训,place,she,still,CSP,模拟,know
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18432110

相关文章

  • [33](CSP 集训)CSP-S 模拟 4
    A商品对于任意一组相邻的数\((l,r)\(l\ler)\),可以发现,不管怎么压缩,都会有\(l\ler\),也就是说,相邻两个数的大小关系是不变的那么我们就可以把\(\sum(|\max-\min|)\)拆出来,变成\[\sum(\max-\min)=\sum(\max)-\sum(\min)\]所以我们可以每对数里的\(\max\)和\(\min\)都......
  • CSP-J/S 2024游记
    24.9.21距离CSP-J/S2024第一轮还有0天。距离停课集训还有1天。集训日子加载中……24.9.22距离CSP-J/S2024第二轮还有33天。初赛成绩已出J:86S:68.5。今日份模拟赛初中联考期望:90+30+0+0=120,实际:90+30+0+0=120,大众分:100+40+40+......
  • NOIP2024模拟赛8 赛后总结
    前言真正的宝石纵使无光,亦能闪耀。今天的纯唐氏题目我居然不会做。考试的时候脑子跟生锈了一样。考虑到\(1,2\)题都太一眼了,这里就只总结一下最后两道题。多重集这道题目的重点是去观察对于\(a_x,b_x,a_y,b_y\)什么条件下\(a_x+a_y\)更小,以及什么条件下\(b_x+b_y\)......
  • 20240925 模拟赛总结
    期望得分:100+85+30+0=215实际得分:100+65+30+0=195。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。还是没啥长进哈。T1二进制位数是关键一招,位数相同怎么异或都会小,位数不同怎么异或都......
  • [湖北省选模拟 2023] 棋圣 / alphago 题解
    很牛的题目啊。-Alex_Wei发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。容易发现若为二分图,则初始颜色不同的一定不能移动到一起。又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令\(c_{i,j}\)为初......
  • 2024.9.2-CSP模拟赛1
    考试:大约在9:40左右发了题。9:45把所有的题目都快速看了一遍,T1感觉模拟可能会T,T2最小生成树的板子,T3又是追及问题感觉要挂,T4感觉像是区间DP。9:50开始做T1,先是手搓了一个gcd又手动模拟了取模(想起了xqy因为取模导致的TLE),样例输出得都挺快的。但是看了一眼数据......
  • 2024.9.3-CSP模拟赛2
    考试:9:00开题:第一题第一眼数据范围\(1\len\le5\times10^7\),感觉有T的风险。第二题littlebird,记得在以前做过这道题。第三题不太会,没有给部分分的比值,感觉只能写个暴搜。\(O(n^2)\)的暴力肯定会,正解先待会再想。9:10做T1,直接写暴力,5分钟写完了。试了一下500......
  • 2024.9.5-CSP模拟赛4
    考试:9:00~9:10看题:T1:很久之前做过,没有什么印象了。T2:感觉是广搜,但有可能要爆。T3:搜索题,猛加优化。T4:不知道是什么类型的题目。9:10~9:50写T1,已经忘了怎么写的,只能当做一道新题来做。写了个贪心,分了2中情况进行讨论,样例和自造样例都过了,但肯定会WA。其实在写计算的......
  • 2024.9.4-CSP模拟赛3
    考试:9:00~9:25怎么还不发卷啊,等得有点慌了,这是在考验心态吗?原来是极域出了点问题9:25~9:35发卷了,先看题。T1:相对距离,这不是原题吗,这题能做。T2:平衡队列,数据有点大,要不要离散化?好像不用,先等会在仔细看看。T3:第一眼数据范围:\(1\leN\le100\),直接弗洛伊德呀。T4:是并查集吗......
  • 2024.9.6-CSP模拟赛5
    考试:9:00~9:10发卷:T1有想法但要思考一下。T2水题,秒切。T3状压,昨天晚上就在看,但没看完只听了思路。T4看上去是原题,可以做一做。9:10~9:30先做T4,真是原题,直接写。直接写了归并排序,前面又补了一个0,然后求了逆序对。样例很快就过了就放了。9:30~9:50直接写了T2,T2......