首页 > 其他分享 >暑假集训csp提高模拟17

暑假集训csp提高模拟17

时间：2024-08-10 17:49:01浏览次数：8  
标签：freopen 17 int long 集训 FILE using csp define

赛时rank16，T1 100,T2 50,T3 25,T4 25

T4是简单题，但因为转移方程没有继承上一位状态，然后就挂了

T3写了个神秘的状压，打了25的部分分

T2暴力，T1正解

T1 符号化方法初探

[ABC081D] Non-decreasing

考虑最大值和最小值

若\(abs(max) > abs(min)\)，则将所有的负数加上最大值使其变为正，前缀和即可

反之，将所有的正数加上最小值使其变为负，后缀和即可

(赛时在这题上唐了又唐)

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 1e5 + 10;
int n,a[N];
#define pii pair<int,int>
#define mk make_pair
//int mx = INT_MIN,mxpos = 0,mn = INT_MAX,mnpos = 0;
set<pii> s;
inline int get(double x){
    if(x < 0) return floor(x);
    else return ceil(x);
}
inline void solve(){
    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i],s.insert(mk(a[i],i));
    vector<pii> ans;
    auto mn = *s.begin(),mx = *s.rbegin();
    if(abs(mx.first) >= abs(mn.first)){
        for(int i = 1;i <= n; ++i){
            if(a[i] < 0) a[i] += mx.first,ans.push_back(mk(mx.second,i));
        }
        for(int i = 2;i <= n; ++i){
            a[i] += a[i - 1];
            ans.push_back(mk(i-1,i));
        }
    }
    else{
        for(int i = 1;i <= n; ++i){
            if(a[i] > 0) a[i] += mn.first,ans.push_back(mk(mn.second,i));
        }
        // for(int i = 1;i <= n; ++i) cerr<<a[i]<<' ';
        // cerr<<'\n';
        for(int i = n - 1;i >= 1; --i){
            a[i] += a[i + 1];
            ans.push_back(mk(i+1,i));
        }
        // for(int i = 1;i <= n; ++i) cerr<<a[i]<<' ';
    }
    cout<<ans.size()<<'\n';
    for(auto i : ans) cout<<i.first<<' '<<i.second<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

T2 无标号 Sequence 构造

#5825.矩阵

奇怪的随机化

我们可以随机一个向量\(\bm b\)，当\(AB=C\)时，即\(\bm bAB=\bm bC\)

然后三次矩阵乘法求左边和右边即可

错误的概率为\(998244353^{-1}\)，题解说证明要用到秩-零化度定理，不会……

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
inline int read(){
    int x = 0;char s = getchar();
    for(;s < '0' || '9' < s;s = getchar());
    for(;'0' <= s && s <= '9';s = getchar())
        x = (x<<1) + (x<<3) + (s^48);
    return x;
}
const int N = 3010,mod = 998244353;
int n,a[N][N],b[N][N],c[N][N],res[N][N],rnd1[N],rnd2[N];
int v1[N],v2[N];
inline void solve(){
    mt19937 rnd((ull)(new char));
    int T;T = read();
    while(T--){
        n = read();
        for(int i = 1;i <= n; ++i) rnd1[i] = rnd2[i] = rnd()%mod+1;
        for(int i = 1;i <= n; ++i)for(int j = 1;j <= n; ++j) a[i][j] = read();
        for(int i = 1;i <= n; ++i)for(int j = 1;j <= n; ++j) b[i][j] = read();
        for(int i = 1;i <= n; ++i)for(int j = 1;j <= n; ++j) c[i][j] = read();
        for(int i = 1;i <= n; ++i){
            v1[i] = 0;
            for(int j = 1;j <= n; ++j) 
                v1[i] = (v1[i] + 1ll*b[i][j]*rnd1[j]%mod)%mod;
        }
        for(int i = 1;i <= n; ++i) rnd1[i] = v1[i];
        for(int i = 1;i <= n; ++i){
            v1[i] = 0;
            for(int j = 1;j <= n; ++j) 
                v1[i] = (v1[i] + 1ll*a[i][j]*rnd1[j]%mod)%mod;
        }
        for(int i = 1;i <= n; ++i){
            v2[i] = 0;
            for(int j = 1;j <= n; ++j)
                v2[i] = (v2[i] + 1ll * c[i][j]*rnd2[j]%mod)%mod;
        }
        bool flag = true;
        for(int i = 1;i <= n; ++i){
            if(v1[i] != v2[i]){
                flag = false;
                break;
            }
        }
        puts(flag?"Yes":"No");
    }
}
signed main(){
    //cin.tie(nullptr)->sync_with_stdio(false);
    //cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

T3 无标号 Multiset 构造

暴力打表题，赛时胡了一个25pts的状压

考虑 \(k\) 很小，对某一行，选择方案只有 \(2^{k}\) 种。因此我们可以将方案按出现哪些行选择方案归类，可以发现只有 \(2^{2^k}\) 种。可以暴力筛出来每种行选择方案是否联通，假设这种方案里有 \(m\) 种行选择方案，那贡献就是 \(n\) 个彼此不同的小球放在 \(m\) 个彼此不同的盒子里，每个盒子至少放一个，根据十二重计数法答案显然是 \(\sum_{i\ge 0} (-1)^{m - i} \binom{m}{i} i^n\)。由于 \(m\le 2^k\)，可以做到 \(O(2^k \log n)\) 求每种可能。

总时间复杂度 \(O(2^{k + 2^k} + 2^k \log n)\)。然而 \(k = 5\) 时预处理的时间爆了。但你发现计算答案时只需要 \(2^k\) 个不同的 \(m\)，而这是好存储的。我们可以对每个 \(k, m\) 打出在 \(2^k\) 种方案中选择 \(m\) 种行的选择方案的表，计算时只需要查询即可。打表程序可能要跑个半小时，所以这题最好早点开 /cy

总时间复杂度 \(O(2^k \log n)\)。

贺的官方题解

打表代码：

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
vector<int> state,ok;
int n,k;
ll ans[10000];
bitset<10000> vis;
inline void check(int have){
    if(!have) return ans[0]++,void();
    int sta = 0,tot = 0;
    sta |= ok[0];
    for(auto i : ok) if(i&sta) tot+=vis[i],vis[i] = false,sta |= i;
    for(auto i : ok) if(i&sta) tot+=vis[i],vis[i] = false,sta |= i;
    for(auto i : ok) if(i&sta) tot+=vis[i],vis[i] = false,sta |= i;
    for(auto i : ok) if(i&sta) tot+=vis[i],vis[i] = false,sta |= i;
    for(auto i : ok) if(i&sta) tot+=vis[i],vis[i] = false,sta |= i;
    for(auto i : ok) vis[i] = true;
    if(tot == have) ans[tot]++;
}
void dfs(int now,int have){
    if(now == (1<<k)){check(have);return;}
    dfs(now + 1,have);
    ok.push_back(now);vis[now] = true;
    dfs(now + 1,have + 1);
    ok.pop_back();vis[now] = false;
}
inline void solve(){
    for(k = 0;k <= 4; ++k){
        vis.reset();
        cout<<k<<":\n";
        vector<int> ().swap(ok);
        dfs(1,0);
        ans[0] = 1;
        for(int i = 0;i <= 32; ++i) cout<<ans[i]<<',';
        cout<<"\n\n\n";
        memset(ans,0,sizeof ans);
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

提交代码:

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
vector<vector<ll> > ans ={
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,3,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,7,15,28,32,21,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,15,80,373,1222,2857,4918,6407,6431,5005,3003,1365,455,105,15,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,31,375,3860,28845,162440,720491,2603950,7856260,20127820,44327130,84657300,141113700,206250800,265182000,300540120,300540190,265182525,206253075,141120525,84672315,44352165,20160075,7888725,2629575,736281,169911,31465,4495,465,31,1,0}
};
inline int power(int a,int b,int mod){
    int res = 1;
    a %= mod;
    for(; b;b >>= 1,a = 1ll * a * a % mod)
        if(b&1) res = 1ll * res * a % mod;
    return res;
}
int fac[100],inv[100];
int k,mod;
ll n;
inline int C(int n,int m){
    if(m > n) return 0;
    if(!m) return 1;
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int la[100];
inline void solve(){
    cin>>n>>k>>mod;
    fac[0] = 1;
    for(int i = 1;i <= 40; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[40] = power(fac[40],mod-2,mod);
    for(int i = 39;i >= 0; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    for(int i = (1<<k);i >= 1; --i) ans[k][i] = (ans[k][i - 1] + ans[k][i]) % mod;
    for(int i = 1;i <= (1<<k); ++i){
        la[i] = power(i,n,mod);
        for(int j = i - 1;j >= 1; --j) la[i] = (la[i] - 1ll * C(i,j) * la[j] % mod + mod) % mod;
    }
    int res = 0;
    for(int i = 1;i <= (1<<k); ++i) res = (res + 1ll * la[i] * ans[k][i] % mod) % mod;
    cout<<res;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();    
}

T4 有限制的构造

\(O(nV^2)\)的背包非常好想，但时空上都不允许。

考虑状态设计优化，将其中一维改为答案，然后枚举答案

\(f_{i,j,k}\)表示已经到了第i个，选择了j个游戏，选择的\(a\)和为k时，b的和的最小值

有

\[f_{i,j,k} = \min(f_{i-1,j-1,k-a_i}+b_i,f_{i-1,j,k}) \]

滚动数组优化可有可无

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 81,V = 1e4 + 10;
int f[2][N][V],n,A,B,a[N],b[N];
inline void solve(){
    cin>>n>>A>>B;
    for(int i = 1;i <= n; ++i) cin>>a[i]>>b[i];
    memset(f,0x3f,sizeof f);
    f[0][0][0] = 0;
    for(int i = 1;i <= n; ++i){
        for(int k = 0;k <= A; ++k) f[i&1][0][k] = f[(i-1)&1][0][k];
        for(int j = 1;j <= i; ++j){
            for(int k = 1;k <= A; ++k) f[i&1][j][k] = f[(i-1)&1][j][k];//赛时因为没写这一行挂了75pts
            for(int k = a[i];k <= A; ++k){
                f[i&1][j][k] = min(f[(i-1)&1][j][k],f[(i-1)&1][j-1][k-a[i]] + b[i]);
            }
        }
    }
    int ans = 0;
    for(int i = 0;i <= A; ++i){
        for(int j = 0;j <= n; ++j){
            if(f[n&1][j][i] <= B) ans = max(ans,j);
        }
    }
    cout<<min(ans+1,n);
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

标签：freopen,17,int,long,集训,FILE,using,csp,define
From： https://www.cnblogs.com/hzoi-Cu/p/18352584

相关文章

  • 『模拟赛』暑假集训CSP提高模拟17
    RankA.符号化方法初探原[ABC081D]Non-decreasing挺水的，不过赛时想了错解。赛时做法是都塞到一个set里一遍推过去，如果比上一个小就lower_bound找一个最接近差的数加上，不过它存在比较大的问题。首先全是负判不了，会进入死循环；其次用map存下标也会出现存在两个相同的......
  • 【大作业-17】使用TensorFlow快速实现图像风格迁移系统
    使用TensorFlow快速实现图像风格迁移系统资源地址：28-基于Tensorflow的风格迁移+代码+模型+系统界面+教学视频.zip资源-CSDN文库视频地址：[使用Tensorflow实现图像风格迁移系统_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1VE421w7RY/)随着GPT的横空出世，生成......
  • springboot垂钓服务系统-计算机毕业设计源码17434
    摘要本文旨在针对垂钓爱好者的需求，基于微信小程序平台，设计并实现一套垂钓服务系统。首先，通过对用户需求进行调研和分析，确定了系统的基本功能模块，包括垂钓点信息展示、用户预约和支付、钓具租赁信息等。接着，借助微信小程序提供的开发框架和组件库，实现了系统的界面设计和交互功......
  • 暑假集训CSP提高模拟17
    暑假集训CSP提高模拟17组题人：@joke3579\(T1\)P222.符号化方法初探\(70pts\)原题：[ABC081D]Non-decreasing部分分测试点\(1\)：输出样例\(1\)。测试点\(11\sim15\)：由于\(\{a\}\)非负，所以对\(\{a\}\)作前缀和即可。随机\(pts\)：乱搞。正解当......
  • P9750 [CSP-J 2023] 一元二次方程题目总结
    根据题面，我们将分为多种情况讨论：若a为负数，那么将a,b,c全部取反首先求出data=b^2-4*a*c;1，data<=0cout<<”NO”;否则带入求跟公式：-b/2a+(-)sqrt(data)注意：：gcd(a,b)有可能为负数，此处应用abs(x)取绝对值若开根号data为有理数{-b为2*a的倍数则直接输出b否则输出b/gcd(b,2*a......
  • 升级到iOS 18、降级回iOS 17
    热烈欢迎，请直接点击！！！进入博主AppStore主页，下载使用各个作品！！！注：博主将坚持每月上线一个新app！！ 苹果官方下载链接：【操作系统OperatingSystems】：https://developer.apple.com/download/【应用Applications】：https://developer.apple.com/download/applications/【描述文件Pr......
  • P1725 琪露诺 题解
    思路动态规划，单调队列动态规划观察题目，发现下标为\(i\)的点只能对\([i+l,i+r]\)区间的点产生贡献。设\(f_i\)为到达点\(i\)时的最大冻结指数。易得状态转移方程式：\(f_k\leftarrow\max(f_k,f_i+a_k),(k\in[i+l,i+r])\)。若直接对该方程进行转移，时间复......
  • P10008 [集训队互测 2022] Range Minimum Element
    MyBlogsP10008[集训队互测2022]RangeMinimumElement难点在于双射构造。首先考虑给定了\(b\)如何进行判定。从小到大填数\(x\)，每次把能填的地方（\(b_i>x\)的区间之外）全部填上\(x\)，这样填一定是最优的。合法当且仅当这样生成的序列\(a\)对应的\(b\)就是\(b\)本身......
  • 2024暑假集训测试20
    前言比赛链接。状态不太好，又犯了老毛病死磕T1，但T1是个很典的套路题我根本没听说过，T2做过原题但没打。T1九次九日久重色详细记录一下这个经典套路。求最长上升子序列\(O(n^2)\)的就不写了，但是记录路径或方案书必须用\(O(n^2)\)，这里说如何\(O(n\logn)\)求。因为......
  • 2024暑假集训测试19
    前言比赛链接。T1因为忘记判一个东西挂分，听说还有被卡哈希的，题目若按照难度正序的话应该是T2、T1、T4、T3，T4看到图论就比较胆怯没怎么想，T3当然没想出来。总而言之T1挂分的人挺多的，T2都能做出来，T1不挂分的排名都很靠前。打得……不算很唐吧，除了T1挂分。T1串串......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99