首页 > 其他分享 >USACO2023 Cu,Ag,Au 题解

USACO2023 Cu,Ag,Au 题解

时间：2023-12-19 21:35:01浏览次数：32  
标签：USACO2023 const int 题解 cin long Au tie include

晚上没事干，于是写了。

Cu：1 h 25 min

Ag：2 h 40 min

Au：2 h 15 min

做最久的竟然是 Ag T1。

Cu

T1

诈骗题，做了 50 min。考虑如果越过了 \(a_i\) 往后走，那么 \(a_i\) 的高度至少翻了一倍。

直接模拟即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n,m,a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(m--)
    {
        int x=1,y;cin>>y;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=x)
            {
                int t=a[i]+1;
                a[i]+=min(a[i],y)-x+1;
                x=t;
            }
            if(x>y) break;
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<'\n';
}

T2

求出至多可以传染多少天，设为 \(d\)，对于每个极长连续段，求出 \(d\) 天传染完最少需要多少奶牛。

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+5;
int n,m,d=1e9,a[N];
char s[N];

int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1,j;i<=n;i++)
        if(s[i]=='1')
        {
            int j=i;
            while(j+1<=n&&s[j+1]=='1') j++;
            int l=j-i+1;
            a[++m]=l;
            if(i==1||j==n) d=min(d,j-i);
            else
            {
                if(l&1) d=min(d,(l-1)/2);
                else d=min(d,(l-2)/2);
            }
            i=j;
        }
    int ans=0;
    d=d<<1|1;
    for(int i=1;i<=m;i++) ans+=ceil(a[i]*1.0/d);
    cout<<ans<<'\n';
}

T3

可以发现植物的高度可以表示为一次函数。按所有直线的 rank 排序，限制变为直线 \(y_i=k_ix+b_i>y_{i+1}=k_{i+1}x+b_{i+1}\)，求交点每次缩小范围即可，注意分类讨论。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n;
struct node{int k,b,rk;} a[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].b;
    for(int i=1;i<=n;i++) cin>>a[i].k;
    for(int i=1;i<=n;i++) cin>>a[i].rk;
    sort(a+1,a+1+n,[&](node a,node b){return a.rk<b.rk;});
    int l=0,r=1e9;
    for(int i=1;i<n;i++)
    {
        auto [k1,b1,r1]=a[i];
        auto [k2,b2,r2]=a[i+1];
        if(k1==k2) {if(b2>=b1) {cout<<-1<<'\n';return;}continue;}
        int x=(b1-b2)/(k2-k1),f=((b1-b2)%(k2-k1)==0);
        if(x<0) continue;
        if(b1>=b2) r=min(r,x-f);
        else l=max(l,x+1);
    }
    if(l>r) cout<<-1<<'\n';
    else cout<<l<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
}

Ag

T1

贪心。按 \(w_i\) 排序。我们只用考虑当前重 \(w_i\) 的奶牛有多少能叠到之前。单调队列维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n,m,k,ans;
struct cow{int w,c;} a[N];
deque<cow> q;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;
    sort(a+1,a+1+n,[&](cow a,cow b){return a.w<b.w;});
    q.push_back({-k,m});
    for(int i=1;i<=n;i++)
    {
        auto [w,c]=a[i];
        int _c=c;
        while(q.size()&&q.front().w+k<=w)
        {
            if(q.front().c<c) c-=q.front().c,q.pop_front();
            else {q.front().c-=c;c=0;break;}
        }
        ans+=_c-c;
        q.push_back({w,_c-c});
    }
    cout<<ans<<'\n';
}

T2

只考虑对 \(b\) 左移，然后 reverse 一下再算一遍。考虑让两个值相同需要左移多少，用桶 \(t\) 统计让 \(b\) 数组左移 \(i\) 位能让多少值相同，取个 max 即可。

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,k,ans,a[N],b[N],t[N],pa[N],pb[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++) cin>>a[i],t[a[i]]++,pa[a[i]]=i;
    for(int i=1;i<=k;i++) cin>>b[i],t[b[i]]++,pb[b[i]]=i;
    for(int i=1;i<=n;i++) ans+=!t[i];
    memset(t,0,sizeof(t));int mx=0;
    for(int i=1;i<=n;i++) if(pa[i]&&pb[i]) t[(pa[i]-pb[i]+k)%k]++;
    for(int i=0;i<=k;i++) mx=max(mx,t[i]);
    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++) if(pb[i]) pb[i]=k-pb[i]+1;
    for(int i=1;i<=n;i++) if(pa[i]&&pb[i]) t[(pa[i]-pb[i]+k)%k]++;
    for(int i=0;i<=k;i++) mx=max(mx,t[i]);
    cout<<ans+mx<<'\n';
}

T3

傻逼细节分讨题。记 所有字符为 F 的位置集合为 \(P\)。

那么改变当前字符 \(c_i\) 可能让后面所有 \(j\in P,j>i\) 左移一位，左移两位，右移一位，右移两位。

对着四种情况分别开一个桶，分类讨论维护一下。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+15;
char s[N];
int n,m,ans,cl1,cl2,cr1,cr2,a[N],t[N],_t[N],p[N],tl1[N],tl2[N],tr1[N],tr2[N];
vector<int> pos;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=m+2,t[a[i]]=1;
    scanf("%s",s+1);
    memcpy(_t,t,sizeof(t));
    p[0]=m+2;
    for(int i=1;i<=m;i++)
    {
        if(s[i]=='L') p[i]=p[i-1]-1;
        if(s[i]=='R') p[i]=p[i-1]+1;
        if(s[i]=='F') p[i]=p[i-1],ans+=t[p[i]],t[p[i]]=0,pos.push_back(p[i]);
    }
    memcpy(t,_t,sizeof(t));
    for(int i:pos)
    {
        if(t[i-1]&&!tl1[i-1]++) cl1++;
        if(t[i-2]&&!tl2[i-2]++) cl2++;
        if(t[i+1]&&!tr1[i+1]++) cr1++;
        if(t[i+2]&&!tr2[i+2]++) cr2++;
    }
    for(int i=1;i<=m;i++)
    {
        int x=p[i];
        if(s[i]=='L') ans=max(ans,cr1+(t[x+1]&&!tr1[x+1])),ans=max(ans,cr2);
        if(s[i]=='R') ans=max(ans,cl1+(t[x-1]&&!tl1[x-1])),ans=max(ans,cl2);
        if(s[i]=='F')
        {
            if(t[x-1]&&!--tl1[x-1]) cl1--;
            if(t[x-2]&&!--tl2[x-2]) cl2--;
            if(t[x+1]&&!--tr1[x+1]) cr1--;
            if(t[x+2]&&!--tr2[x+2]) cr2--;
            ans=max(ans,max(cl1,cr1));
            if(t[x]&&!tl1[x]++) cl1++;
            if(t[x]&&!tl2[x]++) cl2++;
            if(t[x]&&!tr1[x]++) cr1++;
            if(t[x]&&!tr2[x]++) cr2++;
        }
    }
    cout<<ans<<'\n';
}

Au

T1

最简单的 T1

以两个城市的间隔为阶段，进行一个类似 floyd 的过程。

假设当前两个城市为 \(i,j\)，先计算出之前 \(i\rightarrow j\) 的路径数奇偶性。

如果不同，那么添加一条道路。

注意可能重复统计路径，我们枚举和 \(i\) 直接连边的点 \(k\)，只统计 \(k\rightarrow j\) 的路径数。

#include<bits/stdc++.h>
using namespace std;

const int N=755;
char a[N][N];
int n,ans,f[N][N];
vector<int> p[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            cin>>a[i][j],a[i][j]-='0';
    for(int l=1;l<n;l++)
        for(int i=1,j=i+l;j<=n;i++,j++)
        {
            for(int k:p[i]) f[i][j]^=f[k][j];
            if(f[i][j]!=a[i][j]) f[i][j]=a[i][j],p[i].push_back(j),ans++;
        }
    cout<<ans<<'\n';
}

T2

倍增 + Hash。

先建出反图，然后在 DAG 上拓扑转移。

比较两个相同长度的字符串的字典序用倍增 + 哈希。

然后这题还卡 Hash。建议乱搞哈希值，乱取模数。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;

const int N=2e5+5,base=114514;
int n,m,d[N],f[N][20],g[N][20],l[N],ans[N];
ull hs[N][20],ht[N][20],pw[N];
vector<pair<int,int>> G[N];

void get(int u,int v,int w)
{
    l[u]=l[v]+1,g[u][0]=v,ht[u][0]=w;
    for(int i=1;i<=17;i++)
    {
        g[u][i]=g[g[u][i-1]][i-1];
        ht[u][i]=w*base+ht[u][i-1]*pw[1<<i-1]+ht[g[u][i-1]][i-1];
    }
}

int dfs(int u)
{
    if(!u) return 0;
    if(ans[u]) return ans[u];
    return ans[u]=dfs(f[u][0])+hs[u][0];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base;
    for(int i=1;i<=m;i++)
    {
        int u,v,l;cin>>u>>v>>l;
        G[v].push_back({u,l}),d[u]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto [v,w]:G[u])
        {
            if(l[u]+1>l[v])
            {
                l[v]=l[u]+1;get(v,u,w);
                memcpy(f[v],g[v],sizeof(f[v]));memcpy(hs[v],ht[v],sizeof(hs[v]));
            }
            if(l[u]+1==l[v])
            {
                get(v,u,w);
                int x=v,y=v;
                for(int i=__lg(l[v]);~i;i--)
                    if(f[x][i]&&ht[x][i]==hs[y][i]) x=g[x][i],y=f[y][i];
                if(ht[x][0]<hs[y][0]) memcpy(f[v],g[v],sizeof(f[v])),memcpy(hs[v],ht[v],sizeof(hs[v]));
            }
            if(!--d[v]) q.push(v);
        }
    }
    for(int i=1;i<=n;i++) ans[i]=dfs(i);
    for(int i=1;i<=n;i++) cout<<l[i]<<" "<<ans[i]<<'\n';
}

T3

对于每个位置 \(i\)，可以求出一个点对 \((x_i,y_i)\)，选当前点的答案为 \(ax_i+by_i\)。

可以发现随着 \(i\) 的增大，\(x_i\) 是递增的，\(y_i\) 是递减的。不妨把 \(y_i\) 取反，两个值都递增。

\(ax_i+by_i<ax_j+by_j\)

\(a(x_i-x_j)<b(y_j-y_i)\)

\(\frac{x_i-x_j}{y_j-y_i}<\frac{b}{a}\)

相当于坐标系上有一些点对 \((x_i,y_i)\)，用斜率为 \(\frac{b}{a}\) 的直线去切，二分即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int n,m,q,a,b,V=1e6,c[N],s[N],v[N];
struct node{int x,y;} p[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;i++) cin>>x,s[x]+=x,c[x]++,v[x]=1;
    for(int i=1;i<=V;i++) s[i]+=s[i-1],c[i]+=c[i-1];
    for(int i=0;i<=V;i++)
        if(v[i])
        {
            int a=(i-1>=0?c[i-1]*i-s[i-1]:0),b=s[V]-s[i]-(n-c[i])*i;
            p[++m]={a,-b};
        }
    cin>>q;
    while(q--)
    {
        cin>>a>>b;
        int l=1,r=m,ans=1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a*(p[mid].x-p[mid-1].x)<b*(p[mid].y-p[mid-1].y)) ans=mid,l=mid+1;
            else r=mid;
        }
        cout<<a*p[ans].x-b*p[ans].y<<'\n';
    }
}

标签：USACO2023,const,int,题解,cin,long,Au,tie,include
From： https://www.cnblogs.com/spider-oyster/p/17914799.html

相关文章

  • CF1913 E Matrix Problem 题解
    LinkCF1913EMatrixProblemQuestion给定一个\(n\timesm\)的01矩阵，你可以把矩阵中的任意一个元素01翻转需要最后的矩阵满足，每行\(1\)的个数有\(A[i]\)个，每列\(1\)的个数有\(B[i]\)个Solution这貌似是一道非常经典的费用流题目我们建立\(n\)个行节点，\(m......
  • 2023强网杯ez_fmt题解及进阶格式化之劫持子函数
    格式化任意内存读写相信已经是老生常谈了，但是随着题目难度加大，格式化题目给我们的难题逐渐变成了覆写什么，改写什么。这题对我是一道很好的例题，其中对栈及函数调用的理解堪称刷新我的认知。exp先放着，想自己调试理解的可以看看。frompwnimport*context(terminal=['tmux','......
  • MAUI开发笔记（二）
    今天试了一下，在MAUI上调用WEBAPI。经常一番努力，终于调用成功。不过这里面还是有很多的坑。MAUI分了好几个平台，一般来说，最容易成功的是Windows平台。坑1：HttpClient的方法总体来说，其实是用HttpClient来调用。但是HttpClient的方法使用上，也有坑。最开始我使用的是下面的一些接......
  • CSP2023-12树上搜索题解
    刚考完csp，这道题是大模拟题，题意不难理解。以下是题目链接：http://118.190.20.162/view.page?gpid=T178当时考场上这道题调了好久没调出来，忽略了很多细节。在这里分享一下满分题解及思路，帮大家避避坑。#include<iostream>#include<stdio.h>#include<queue>#include<cstring>#inc......
  • syoj.1827. 线段传送带题解
    前情提要-三分1827.线段传送带P2571[SCOI2010]传送带省流：三分套三分。在二维平面上有两个传送带，一个从A点到B点，一个从C点到D点，速度分别是p和q，在平面内其他点的速度为r。求A点到D点的最小速度。考虑从A到D的路程一定是\(AE+EF+FD\)，即通过这两个点连......
  • 智慧安防视频监控可视化平台EasyCVR调用接口返回“Unauthorized”是什么原因？
    智慧安防视频监控可视化平台EasyCVR采用了开放式的网络结构，平台能在局域网、公网、专网等复杂的网络环境中，将场景中分散的海量网络监控设备进行统一接入与汇聚管理，并能提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集......
  • 解决安卓设备无法使用authenticator app问题
    今天要说的是微软的authenticatorapp在中国的使用问题，众所周知的是，微软和很多厂商现在都在大力推广passwordless的身份验证方式，认为username和password已经不再安全，属于要慢慢摒弃的旧方法，至于哪些身份验证方式比较安全，微软心目中认定的身份验证的级别可以参考下图可以看到authent......
  • CF1733D1 题解
    原题传送门题目大意给定两个长度为\(n\)的二进制字符串\(a\)和\(b\)，你可以进行若干次操作，对于每次操作：选两个数\(l\)和\(r\)，且\(l<r\)，将\(a_l\)和\(a_r\)交换。如果选取的\(l\)和\(r\)相邻，代价为\(x\)，否则为\(y\)。保证\(y≤x\)，求出最小代价使得\(a=......
  • CF1191B 题解
    原题传送门题目大意\(3\)块麻将，求需要换掉几张牌才能一次出完\(3\)块麻将。每块麻将，用一个长度为\(2\)的字符串给出，字符串由\((1,9)\)的一位数字和\(m\)、\(s\)或\(p\)组成。\(3\)块一模一样的麻将或第\(2\)位相同，前面是连号的\(3\)块麻将都可以一次性出完。......
  • CF175B 题解
    原题传送门题目大意如题目描述。思路分析\(1≤n≤1000\)，很明显\(\mathcal{O(n^2)}\)不超时，使用结构体，暴力即可。利用双循环求出名字相同的结构体并判断最高分，再根据字典序排序，再双循环求出比自己优秀人数，输出即可。代码：/*Writtenbysmx*/#include<bits/stdc++.h>usin......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99