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

暑假集训csp提高模拟12

时间：2024-07-31 16:17:26浏览次数：11  
标签：12 freopen err int long 集训 FILE using csp

赛时rank 47，T1 100,T2 0,T3 0,T4 20

做题策略不好，没做T2，死在T4上了。

感觉赛时就是唐。

T1 黑客

考虑枚举结果，如果存在贡献，那么一定有\(i+j=k\& gcd(i,j)=1\)，统计一下有多少组即可

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
    FILE *ErrFile = freopen("err.err","w",stderr);
#else
    FILE *InFile = stdin,*OutFile = stdout;
    // FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
#define int long long
const int mod = 1e9 + 7;
ll a,b,c,d;
int f[1000];
signed main(){
    cin>>a>>b>>c>>d;
    for(int k = 1;k <= 999; ++k){
        for(int i = 1;i < k; ++i){
            int j = k - i;
            if(__gcd(i,j) == 1){
                ll up1 = b/i,up2 = d/j;
                ll down1 = (a-1)/i,down2 = (c-1)/j;
                // cerr<<i<<' '<<j<<' '<<min(max(up1-down2,0ll),max(up2-down1,0ll))<<'\n';
                f[k] = (0ll + f[k] + min({max(up1-down2,0ll),max(up2-down1,0ll),max(up1-down1,0ll),max(up2-down2,0ll)}))%mod;
            }
        }
    }
    ll ans = 0;
    for(int k = 1;k <= 999; ++k)
        ans = (ans + 1ll*f[k]*k%mod)%mod;
    cout<<ans;
}

T2 密码技术

[ARC107C] Shuffle Permutation

考虑到无论如何排列都无影响，那么就考虑行和列分开。

将可以互相交换的放入一组，并查集维护，求连通块大小的阶乘。

行列贡献相乘

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
    // FILE *ErrFile = freopen("err.err","w",stderr);
#else
    FILE *InFile = stdin,*OutFile = stdout;
    // FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
const int N = 51,mod = 998244353;
int n,k;
int a[N][N],sum1[N],sum2[N],fa[N],siz[N];
int get_fa(int x){return (x == fa[x]?x:fa[x] = get_fa(fa[x]));}
signed main(){
    cin>>n>>k;
    for(int i = 1;i <= n; ++i) for(int j = 1;j <= n; ++j) cin>>a[i][j];
    ll ans1 = 0;
    for(int i = 1;i <= n; ++i) fa[i] = i,siz[i] = 1;
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j < i; ++j){
            bool flag = true;
            for(int t = 1;t <= n; ++t){
                if(a[i][t] + a[j][t] > k){flag = false;break;}
            }
            if(flag){
                int fx = get_fa(i),fy = get_fa(j);
                if(fx == fy) continue;
                fa[fx] = fy;
                siz[fy] += siz[fx];
                get_fa(fx);
            }
        }
    }
    // for(int i = 1;i <= n; ++i) cerr<<siz[i]<<' ';
    // cerr<<'\n';
    ll ans = 1;
    for(int i = 1;i <= n; ++i) {
        if(fa[i] == i){
            for(int j = siz[i];j >= 1; --j) ans = ans * j % mod;
        }
    }
    for(int i = 1;i <= n; ++i) fa[i] = i,siz[i] = 1;
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j < i; ++j){
            bool flag = true;
            for(int t = 1;t <= n; ++t){
                if(a[t][i] + a[t][j] > k){flag = false;break;}
            }
            if(flag){
                int fx = get_fa(i),fy = get_fa(j);
                if(fx == fy) continue;
                fa[fx] = fy;
                siz[fy] += siz[fx];
            }
        }
    }
    for(int i = 1;i <= n; ++i) {
        if(fa[i] == i){
            for(int j = siz[i];j >= 1; --j) ans = ans * j % mod;
        }
    }
    cout<<ans;
}

T3 修水管

[HNOI2015] 亚瑟王

发现期望难以转移，于是考虑先处理概率\(g\)

我们有\(ans=\sum_{i=1}^ng_id_i\)

如果一段水管被修复过，那么要么让它之前被修复，要么它没有炸掉。

设\(f_{i,j}\)表示在前\(i\)个位置，在\(r\)轮中修复过\(j\)次的期望。

\[f_{i,j}=f_{i-1,j}\times(1-p_i)^{r-j}+f_{i-1,j-1}\times(1-(1-p_i)^{r-j+1}) \]

\[g_i=\sum_{j=0}^rf_{i-1,j}\times (1-(1-p_i)^{r-j}) \]

点此查看代码 
#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
bool StdIn = cin.tie(nullptr)->sync_with_stdio(false);
bool StdOut = cout.tie(nullptr)->sync_with_stdio(false);
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 300;
db f[N][N],g[N],p[N];
int n,d[N],r;
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n>>r;
        for(int i = 1;i <= n; ++i) cin>>p[i]>>d[i];
        memset(f,0,sizeof f);memset(g,0,sizeof g);
        f[0][0] = 1;
        for(int i = 1;i <= n; ++i){
            for(int j = 0;j <= r; ++j){
                f[i][j] = f[i-1][j] * pow(1-p[i],r-j);
                if(j) f[i][j] += f[i-1][j-1]*(1-pow(1-p[i],r-j+1));
            }
        }
        for(int i = 1;i <= n; ++i)
            for(int j = 0;j <= r; ++j) 
                g[i] += f[i-1][j]*(1-pow(1-p[i],r-j));
        db ans = 0;
        for(int i = 1;i <= n; ++i) ans += g[i]*d[i];
        cout<<fixed<<setprecision(10)<<ans<<'\n';
    }
}

T4 货物搬运

Serega and Fun

deque/vector+分块

暴力删，暴力跑即可

这么简单的题我场上没切真是唐！

时间复杂度单次操作\(O(\sqrt {n})\)

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
    // FILE *ErrFile = freopen("err.err","w",stderr);
#else
    FILE *InFile = stdin,*OutFile = stdout;
    // FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
const int N = 1e5+10,M = sqrt(N)+10;
int n,q,a[N],pos[N],L[N],R[N],siz,lastans;
deque<int> Q[320];
int sum[320][N];
signed main(){
    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    siz = sqrt(n);
    for(int i = 1;i <= siz; ++i) L[i] = R[i-1]+1,R[i] = i * siz;
    if(R[siz] < n) siz++,L[siz] = R[siz-1]+1,R[siz] = n;
    for(int i = 1;i <= siz; ++i){
        for(int j = L[i];j <= R[i]; ++j){
            pos[j] = i;
            Q[i].push_back(a[j]);
            sum[i][a[j]]++;
        }
    }
    cin>>q;
    int tot = 0;
    while(q--){
        int op,l,r,k;
        cin>>op>>l>>r;
        l = (l+lastans-1)%n+1;
        r = (r+lastans-1)%n+1;
        if(l > r) swap(l,r);
        if(op == 1){
            int p = pos[r],p1 = pos[l];
            int x = *(Q[p].begin()+(r-L[p]));
            sum[p][x]--;
            Q[p].erase(Q[p].begin()+(r-L[p]));
            if(l == L[p1]) Q[p1].push_front(x);
            else Q[p1].insert(Q[p1].begin()+(l-L[p1]),x);
            sum[p1][x]++;
            for(int i = p1 + 1; i <= p; ++i){
                int x = Q[i-1].back();
                Q[i].push_front(x);
                sum[i][x]++;sum[i-1][x]--;
                Q[i-1].pop_back();
            }
        }
        else{
            tot++;
            cin>>k;k = (k + lastans - 1) % n + 1;
            int p = pos[l],q = pos[r],res = 0;
            if(p == q){
                for(int i = l;i <= r; ++i) 
                    res += (Q[p][i-L[p]] == k);
            }
            else{
                for(int i = p + 1;i < q; ++i) res += sum[i][k];
                for(int i = l;i <= R[p]; ++i) 
                    res += (Q[p][i-L[p]] == k);
                for(int i = L[q];i <= r; ++i) 
                    res += (Q[q][i-L[q]] == k);
            }
            cout<<(lastans = res)<<'\n';
        }
    }
}

总结一下吧，毕竟这么唐。

这两天的状态不是很好，集训时间太久了。

休息也没休息好。

打的很难评，赛时怎么也想不出正解，赛后才明白自己场上有多唐。

思维上还是有遗漏，对数学题总是有一种畏惧的心理，怎么想也想不出来。

一些简单题也会因此受影响。

读假题的现象时有发生，比如T2就没有把题读完。然后就似了。

菜是原罪。

马上就要放假了，调整一下，等再回来的时候应该就好了，应该吧……

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

相关文章

  • 洛谷题单指南-前缀和差分与离散化-P1083 [NOIP2012 提高组] 借教室
    原题链接：https://www.luogu.com.cn/problem/P1083题意解读：已知第i天有r[i]个教室可以供租借，有m个租借教室的订单，第i订单需要在第s[i]~t[i]天区间内租借d[i]个教室，计算是否全部订单都能满足，如果不满足要输出从第几个订单开始不满足。解题思路：1、朴素做法枚举1~m个订单，通过差分......
  • 基于ads1292的心电信号采集之芯片关键点备忘
    一前记团队在作基于ads1292的心电数据采集时候，遇到了一些问题。这里做一个记录和备忘。也希望能帮的到同样遇到困难的朋友。 二关注点1reset引脚不能悬空，这个悬空的时候，笔者发现ads1292无法正常工作。  2.start信号在单独使用的时候，不要接GND......
  • 嵌入式学习第12天——C语言循环结构
    循环结构什么是循环代码的重复执行，就叫做循环。循环的分类无限循环：程序设计中尽量避免无限循环（程序中的无限循环必须可控）。有限循环：循环限定循环次数或者循环的条件。循环的构成循环体循环条件当型循环的实现while语法： while(循环条件) { 循环语句；......
  • 21LTR.com_Scene1_2.120靶机
    getshell主机发现，端口目录扫描只有一个logs目录，接着往下扫访问首页，检查源代码，发现一组账号密码，可能是ssh，也可能是ftp的访问logs接口，没有权限尝试利用发现的账号密码，ssh没有成功，尝试ftp注意在windows上什么没有，用kali连接下载到本地查看一下拼接访问logs目录......
  • 瑞士ABB苏黎世张力控制器PFEA112-20
    其特点是控制电路结构简单、成本较低，机械特性硬度也较好，能够满足一般传动的平滑调速要求，已在产业的各个领域得到广泛应用。但是，这种控制方式在低频时，由于输出电压较低，转矩受定子电阻压降的影响比较显著，使输出大转矩减小。另外，其机械特性终究没有直流电动机硬，动态转矩能力和静态......
  • CSP模拟10--总结
    今天是我第一次给模拟赛写正规总结--因为今天的题真的受不了了四道数学题，一点都不拖泥带水的纯血数学题！T1、黑暗型高松灯shit本来是一道放在T4防AK的题，结果学长为了恶心锻炼一下我们，直接将T1和T4swap了一下.一开始看了半个小时挺懵逼的，然后跳了，但心里一直觉得这题能做......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）1012并
    题目大意：给出n个矩形，求被k个矩形覆盖的面积的并集的期望，输出k为1-n的所一答案思路：由于是求期望所以是求出所有情况的和再除以可能的情况，每一种情况中的面积都由--同时被1个矩形覆盖，同时被两个矩形覆盖······同时被k个矩形覆盖组成，而且不难得出当k一定时，取被m个矩形覆盖的......
  • ssy中学暑假集训分数规划笔记
    分数规划出现在了我们今天的模拟赛中，看在这个名字深得我心而且我能看懂证明和内容的份上，给开个专题吧！\(1.定义\)：分数规划就是求分数的极值。形象一点就是，给出\(a_i\)和\(b_i\)，求一组\(w_i\in\{0,1\}\)最小化或者最大化下面的算式：\[\frac{\sum_{i=1}^{n}a_i*w_i}{\sum_{i=1}......
  • 7月30日CSP-S模拟赛赛后总结
    7月30日模拟赛赛后总结\[7月30日\\模拟赛\\赛后总结\\2024年7月30日\\by\\\hcy\]洛谷同步：点我一、做题情况第一题比赛\(100pts\)，赛后\(AC\)第二题比赛\(20pts\)，赛后\(AC\)第三题比赛\(0pts\)，赛后\(AC\)第四题比赛\(30pts\)，赛后\(30pts\)......
  • c# RSA 要解密的数据超过此模块的最大值128/256字节
    publicstringDecrypt(){varbase64EncryptedData="";stringprivateKey=@"<RSAKeyValue>....</RSAKeyValue>";RSACryptoServiceProviderprovider=newRSACryptoServiceProvider();provider.FromXml......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99