首页 > 其他分享 >[VP记录]AGC003

[VP记录]AGC003

时间:2022-11-13 16:45:03浏览次数:48  
标签:AGC003 连通 记录 int long stk VP 100010 ans

以后不放题目链接了。

[AGC003A] Wanna go back home

普及-。

char S[1010];
int len;
bool s,e,n,w;
int main(){
    scanf("%s",S+1);len=strlen(S+1);
    for(int i=1;i<=len;i++){
        if(S[i]=='S')s=true;
        if(S[i]=='N')n=true;
        if(S[i]=='E')e=true;
        if(S[i]=='W')w=true;
    }
    if((s^n)||(e^w))puts("No");
    else puts("Yes");
    return 0;
}

[AGC003B] Simplified mahjong

普及题,贪心就行。

int n,a[100010];
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i-1]&&a[i])a[i]--,a[i-1]--,ans++;
        ans+=a[i]>>1;a[i]&=1;
    }
    printf("%lld\n",ans);
    return 0;
}

[AGC003C] BBuBBBlesort!

然而并没有绿。

离散化之后统计奇数位置上的偶数个数和偶数位置上的奇数个数之和除以 \(2\) 就行(其实这俩应该一样?)。

int n,ans,a[100010],lsh[100010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
        if((a[i]&1)!=(i&1))ans++;
    }
    printf("%d\n",ans>>1);
    return 0;
}

[AGC003D] Anticube

本场应该是最好玩的题。

首先质因子指数显然可以都 \(\bmod 3\)。

然后显然不能暴力跑质因子分解(当然这题其实pr能过)。设值域是 \(mx\) ,那么先分解 \(\sqrt[3]{mx}\) 以内的质因子并统计乘积和乘上之后是完全立方数的数。然后这样剩下了一堆数,开始分讨:

  1. 是 \(1\),单独放一组。
  2. 是个小于 \(\sqrt {mx}\) 的质数,放第二组。
  3. 是个小于 \(\sqrt{mx}\) 的质数的平方,放第三组。
  4. 剩下的可能是一个大质数或者两个小于 \(\sqrt{mx}\) 的数相乘。这样的话能和它乘上后变成完全立方数的最小的数一定超过 \(mx\) ,所以可以直接加入答案。

然后容易发现要么两个第一组的组成一个完全立方数,要么一个第二组一个第三组组一个。讨论即可。

#define int long long
int n,mx,ans,a[100010],b[100010],c[100010],p[100010];
bool v[100010];
map<int,int>mp1,mp2;
vector<int>a1[100010],a2[100010];
void get(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])p[++p[0]]=i;
        for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
            v[i*p[j]]=true;
            if(i%p[j]==0)break;
        }
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),mx=max(mx,a[i]);
    get(3000);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=p[0]&&p[j]*p[j]*p[j]<=a[i];j++){
            int ret=p[j]*p[j]*p[j];
            while(a[i]%ret==0)a[i]/=ret;
        }
    }
    sort(a+1,a+n+1);
    if(a[1]==1)ans++;
    for(int i=1;i<=n;i++){
        if(a[i]==1)continue;
        b[i]=c[i]=1;
        for(int j=1;j<=p[0]&&p[j]<=a[i];j++){
            int cnt=0;
            while(a[i]%p[j]==0)a[i]/=p[j],cnt++;
            if(cnt==1)b[i]*=p[j]*p[j],c[i]*=p[j];
            else if(cnt==2)b[i]*=p[j],c[i]*=p[j]*p[j];
        }
        int sq=sqrt(a[i]);
        if(sq*sq==a[i])a1[sq].push_back(i);
        else if(a[i]<=100000)a2[a[i]].push_back(i);
        else ans++;
    }
    for(int x:a1[1])mp1[b[x]]++;
    for(int x:a1[1])ans+=max(mp1[b[x]],mp1[c[x]]),mp1[b[x]]=mp1[c[x]]=0;
    for(int i=2;i<=100000;i++){
        if(!a1[i].size()||!a2[i].size())ans+=a1[i].size()+a2[i].size();
        else{
            mp1.clear();mp2.clear();
            for(int x:a1[i])mp1[b[x]]++;
            for(int x:a2[i])mp2[b[x]]++;
            for(int x:a1[i])ans+=max(mp1[b[x]],mp2[c[x]]),mp1[b[x]]=mp2[c[x]]=0;
            for(int x:a2[i])ans+=max(mp2[b[x]],mp1[c[x]]),mp2[b[x]]=mp1[c[x]]=0;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

[AGC003E] Sequential operations on Sequence

可能是水黑?

首先我们可以拿个单调栈把所有询问弄成递增的。然后考虑如何增加。

倒着扫,然后假设我们要从 \(q_i\) 增加到 \(q_{i+1}\)。那么我们分两类讨论。

  1. \(k=\dfrac {q_{i+1}}{q_i}\)。这一部分直接把前面集体乘个 \(k\) 就可以。
  2. \(r=q_{i+1}\bmod q_i\)。这一部分如果我们可以找到 \(q\) 中最大的 \(\le q_i\) 的 \(q_x\),那么我们就可以接着把 \(q_{i+1}\) 和 \(q_i\) 的关系变成 \(q_i\) 和 \(q_x\) 的关系。递归即可。递归最后会变成一个区间加,差分就行了。
#define int long long
int n,q,top,a[100010],stk[100010],d[100010];
void getans(int x,int val){
    int pos=upper_bound(stk+1,stk+top+1,x)-stk-1;
    if(pos==0){
        a[1]+=val;a[x+1]-=val;
    }
    else{
        d[pos]+=x/stk[pos]*val;
        getans(x%stk[pos],val);
    }
}
signed main(){
    scanf("%lld%lld",&n,&q);
    stk[++top]=n;
    while(q--){
        int x;scanf("%lld",&x);
        while(top&&stk[top]>=x)top--;
        stk[++top]=x;
    }
    d[top]=1;
    for(int i=top;i>=2;i--){
        d[i-1]+=stk[i]/stk[i-1]*d[i];
        getans(stk[i]%stk[i-1],d[i]);
    }
    a[1]+=d[1];a[stk[1]+1]-=d[1];
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1];
        printf("%lld\n",a[i]);
    }
}

[AGC003F] Fraction of Fractal

知道是矩阵乘法之后可能算还好。

首先显然只有增加一级分形的时候才可能增加连通块。那么我们可以把初始的网格分别向右、向下接一个,判一下是否左右连通和上下连通。于是有三种情况:

  1. 都连通:显然不论什么时候连通块个数都是 \(1\)。
  2. 都不连通:所有连通块不管几级分形都接不上,一个快速幂跑路。
  3. 一边连通,以左右连通为例。上下直接转置成左右即可。

现在我们考虑一边连通的情况。(因为这是个矩阵乘法题,)我们考虑递推出 \(n\) 阶分形的答案。

设黑点个数为 \(cnt\) ,那么每次分形会增加 \(cnt\) 个连通块减去左右已经连通的块数。初始的左右连通块数可以预处理,每次递推的时候这个块数会乘上左右连通的个数。这样我们可以列出一个 \(2\times 2\) 的矩阵,快速幂即可。

写起来好像有点小麻烦所以是∑的。

const int mod=1000000007;
int n,m,cnt,a1,a2,s1,s2;
long long k;
char s[2010][2010];
struct node{
    int a[3][3];
    node operator*(const node &b)const{
        node ret={};
        ret.a[1][1]=(1ll*a[1][1]*b.a[1][1]+1ll*a[1][2]*b.a[2][1])%mod;
        ret.a[1][2]=(1ll*a[1][1]*b.a[1][2]+1ll*a[1][2]*b.a[2][2])%mod;
        ret.a[2][1]=(1ll*a[2][1]*b.a[1][1]+1ll*a[2][2]*b.a[2][1])%mod;
        ret.a[2][2]=(1ll*a[2][1]*b.a[1][2]+1ll*a[2][2]*b.a[2][2])%mod;
        return ret;
    }
}a,b;
node qpow(node a,long long b){
    node ans={};ans.a[1][1]=ans.a[2][2]=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int qpow(int a,long long b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'){
                cnt++;
                if(j>1)a1+=(s[i][j-1]=='#');
                if(i>1)a2+=(s[i-1][j]=='#');
            }
        }
    }
    for(int i=1;i<=n;i++)if(s[i][1]=='#'&&s[i][m]=='#')s1++;
    for(int i=1;i<=m;i++)if(s[1][i]=='#'&&s[n][i]=='#')s2++;
    if(s1!=0&&s2!=0){
        puts("1");return 0;
    }
    if(s1==0&&s2==0){
        printf("%d\n",qpow(cnt,k-1));
        return 0;
    }
    int ret=s2;
    a.a[1][1]=cnt;
    if(!ret)a.a[1][2]=(mod-a1)%mod,a.a[2][2]=s1;
    else a.a[1][2]=(mod-a2)%mod,a.a[2][2]=s2;
    b.a[1][1]=b.a[2][1]=1;
    a=qpow(a,k-1);
    a=a*b;
    printf("%d\n",a.a[1][1]);
    return 0;
}

完了。

标签:AGC003,连通,记录,int,long,stk,VP,100010,ans
From: https://www.cnblogs.com/gtm1514/p/16886254.html

相关文章

  • flink开发中整合flinksql、kafka、mysql、hbase等问题与结果记录
    在flink开发中,通常会配合flinksql、kafka、mysql、hbase等一块使用,为避免jar包缺失、冲突,现整理一下。一、版本说明flink:1.13.0kafka:2.11mysql:8.0hbase:2.2.3二、fl......
  • 【博学谷学习记录】超强总结,用心分享|Requests库以及集成UnitTest实现接口测试案例总
    一,介绍Requests库是一个基于python语言开发的一个开源的库,能够完全满足基于HTTP协议的接口测试。二,安装与验证Requests库的安装:在cmd窗口输入:pipinstallrequests......
  • 22-11-11学习记录
    1,memcpy:内存拷贝(处理内存不重叠情况)2,memmove:内存拷贝(处理内存重叠情况)3,memset:内存设置  void*memset(void*dest,intc,size_tcount);dest:目的地  c:存放的......
  • 记录美化Windows Terminal
    通过OhMyPosh来自定义PowerShell,以提供Git状态提示符,再对WindowsTerminal美化,得到一个优秀的终端体验。获取PowerShellWindows自带的PowerShell是5.x版......
  • LeetCode刷题记录.Day13
    四数之和18.四数之和-力扣(LeetCode)classSolution{public:vector<vector<int>>fourSum(vector<int>&nums,inttarget){vector<vector<int>>res......
  • Spring 事务(测试)--在这个笔记中记录的是没有添加事务,数据库返回的效果。
    第5章Spring事务(测试)--在这个笔记中记录的是没有添加事务,数据库返回的效果。1.首先搞两张表,商品表和订单表举例:购买商品trans_sale项目本例要实现购买商品,模拟用......
  • 数据库一些问题记录
    视图视图是一种虚拟表(虚表)。它基于一张表或多张表(原表)的查询结果。创建一个视图语句如:SELECT*FROM`typecho_contents`WHEREcid>120ORDERBYtypecho_contents.`create......
  • [VP]CF823 Div2
    A.Planets题意:给你一个序列aaa,你可以分别进行如下操作任意次:花费\(1\)的代价删除\(a_i\)花费\(c\)的代价删除\(\foralla_i=x\),\(x\)自定。求删除整个序列......
  • 记录一次保持原电压实现内存超频
    最近身边朋友开始换新型号的电脑,内存也都换成了DDR5的,看着自己手上的几年前的电脑还用这ddr4的内存,想着要不也试试把内存频率调调,也搞个超频试试。 由于最初的想法就是......
  • sql 功能点记录
    1.ORDERBY降序排序之后,值为NULL的排在前边,期望排在后边,只需要在后边加上NULLSLAST,比如:ORDERBYfieldName DESCNULLSLAST2.FULLJOIN全连接之后,需要合并同一个......