2020牛客暑期多校训练营(第二场)
in 牛客多校多校训练 with 2 comments

2020牛客暑期多校训练营(第二场)

in 牛客多校多校训练 with 2 comments

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.All with Pairs

wrf(赛后)

题意

给出若干个字符串,定义 $f(s_i,s_j)$ 为串 $s_i$ 的前缀与串 $s_j$ 的后缀的最大重合长度。
求 $\sum \sum f(s_i,s_j)^2$
总长保证不超过 $10^6$

题解

做法

求出所有后缀的哈希值,用所有前缀匹配它。
注意到对于每一对串,只应该有最大长度的前缀被匹配。这些贡献在该前缀之前的 border 中都被重复计算了。
所以对于每一个前缀,将它 border 处的贡献减去它自己的贡献即可。

时间复杂度

$O(|S|\log |S|)$

代码

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll mod=1231453023109121LL;

const int N=1000200;
 
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
map<pair<int,ll>,int> suf;
char t[N];
ll p131[N];
 
int main(void)
{
    //ios::sync_with_stdio(false);
     
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
 
    p131[0]=1;
    for(int i=1;i<N;i++)
    {
        p131[i]=p131[i-1]*131%mod;
    }
     
    int n=read();
         
    vector<char*> c(n);
    vector<vector<int> > v(n);
    vector<vector<ll> > qzh(n);
    vector<vector<int> > border(n);
    vector<vector<int> > ans(n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",t);
         
        int l=strlen(t);
        c[i]=(char*)malloc((l+1)*sizeof(char));
        strcpy(c[i],t);
 
 
        border[i].resize(l+1);
        qzh[i].resize(l+1);
        ans[i].resize(l+1);
        border[i][0]=0;
        int tj=0;
        for(int j=1;j<l;j++)
        {
            while(tj && t[tj]!=t[j]) tj=border[i][tj];
            if(t[tj]==t[j]) tj++;
            border[i][j+1]=tj;
        }
 
        for(int j=0;j<l;j++)
        {
            qzh[i][j+1]=(qzh[i][j]*131+t[j])%mod;
        }
        for(int j=1;j<=l;j++)
        {
            suf[{j,(qzh[i][l]+mod-ll(__int128(qzh[i][l-j])*p131[j]%mod))%mod}]++;
        }
    }
    for(int i=0;i<n;i++)
    {
        int l=strlen(c[i]);
         
        for(int j=1;j<=l;j++)
        {
            if(qzh[i][j]<0) assert(0);
            if(suf.find({j,qzh[i][j]})!=suf.end())
            {
                ans[i][j]+=suf[{j,qzh[i][j]}];
            }
        }
        for(int j=1;j<=l;j++)
        {
            ans[i][border[i][j]]-=ans[i][j];
        }
    }

    ll s=0;
    for(int i=0;i<n;i++)
    {
        int l=strlen(c[i]);
        for(int j=1;j<=l;j++)
        {
            s=(s+1ll*ans[i][j]*j%998244353*j%998244353)%998244353;
        }
    }
 
    printf("%lld",s);
     
    return 0;
}

B.Boundary

wrf(赛后)

题意

在平面上给若干个点,求一个过原点的圆,使得尽量多的点在圆上。
保证点数不超过 2000,坐标绝对值不超过 10000。

题解

做法

枚举两个点,与原点三点确定一个圆。
求得每个点的圆心位置,用数据结构或排序维护每个圆心的出现次数。

细节

long long 可以没有精度损失。
固定一个点,仅讨论第二个点的出现次数,可以少一些常数。
注意用叉乘判断大小的时候,要把分母全化为正数。

举例: -8/-8>0/4,-8*4<-8*0

map远慢于排序

代码

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

const int N=100020;
 
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct frac
{
    ll x,y;
    bool operator<(const frac& b) const
    {
        return __int128(x)*(b.y)<__int128(y)*(b.x);
    }
    bool operator==(const frac& b) const
    {
        return __int128(x)*(b.y)==__int128(y)*(b.x);
    }
 
 
    frac(ll a=0,ll b=0): x(a),y(b) {}
};
 
struct point
{
    frac x,y;
 
    bool operator<(const point& b) const
    {
        return x==b.x?y<b.y:x<b.x;
    }
    bool operator==(const point& b) const
    {
        return x==b.x && y==b.y;
    }
 
    point(ll a=1,ll b=2,ll c=3,ll d=4): x(b*(c*c+d*d)-d*(a*a+b*b),2ll*(b*c-a*d)),y(-a*(c*c+d*d)+c*(a*a+b*b),2ll*(b*c-a*d)) 
    {
        if(x.y<0) x.x=-x.x,x.y=-x.y;
        if(y.y<0) y.x=-y.x,y.y=-y.y;
    }
};

int q[4000020];
int main(void)
{
    for(int i=1;i<=2000;i++)
    {
        q[i*(i-1)/2]=i;
    }
     
    int n=read();
    vector<ll> a(n),b(n);
    for(int i=0;i<n;i++) a[i]=read(),b[i]=read();
 
    vector<point> qa; 

    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[i]*b[j]==a[j]*b[i]) continue;
            qa.push_back(point(a[i],b[i],a[j],b[j]));
        }
    }

    sort(qa.begin(),qa.end());
    int ans=0,pr=0;
    for(int i=0;i<qa.size();i++)
    {
        if(i==0 || qa[i]==qa[i-1]) pr++;
        else ans=max(ans,pr),pr=1;
    }
    ans=max(ans,pr);
 
    printf("%d",q[ans]);
     
    return 0;
}

C.Cover the Tree

wrf (01:23:51) +2

题意

给出一棵树,要求用若干条链覆盖树的每一条边,链之前可重叠。
要求最小化所用链的数量,输出任意一种方案。

题解

做法

按 dfs 序,所有的[i,i+(n+1)/2]即是解。
如果n为奇数,再连接[1,(n+1)/2]即可。

证明

先令n为偶数。
首先每条链都会包括(n+1)/2+1个点。
假设每条边中高度较大的节点(子节点)的子树在 dfs 序中的区间为[L,R],分类讨论。

如果n为奇数,那么可以补上一条边[1,n+1],然后连边[(n+1)/2,n+1],再将点n+1删去,即[1,(n+1)/2]

时间复杂度

$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct tree
{
    struct node
    {
        int h,w,s,f,t,dfn;
        node(void): h(0),w(0),s(-1),f(0),t(0),dfn(0) {}
    };
    vector<vector<int> > e;
    vector<node> v;
    
    int n;
    int tdfn=1;

    tree(int _n): e(_n+1),v(_n+1),n(_n) {}

    void link(int x,int y) {e[x].push_back(y),e[y].push_back(x);}

    int dfs1(int n=1,int h=1,int fa=1)
    {
        v[n].h=h;
        v[n].w=1;
        v[n].f=fa;
        int mxw=0;
        for(int i=0;i<e[n].size();i++)
        {
            if(v[e[n][i]].h==0)
            {
                int t=dfs1(e[n][i],h+1,n);
                v[n].w+=t;

                if(mxw<t) mxw=t,v[n].s=i;
            }
        }

        return v[n].w;
    }
    void dfs2(int n=1,int f=1)
    {
        v[n].t=f;
        v[n].dfn=tdfn;
        tdfn++;

        if(v[n].s!=-1) dfs2(e[n][v[n].s],f);
        for(int i=0;i<e[n].size();i++)
        {
            if(i!=v[n].s && v[e[n][i]].h>v[n].h)
            {
                dfs2(e[n][i],e[n][i]);
            }
        }
    }
};

tree* tr;

int main(void)
{
    int n=read();
    vector<int> v(n+1);

    tr=new tree(n);
    if(n==1) 
    {
        printf("0");
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        int l=read(),r=read();
        v[l]++;
        v[r]++;
        tr->link(l,r);
    }

    tr->dfs1();
    tr->dfs2();

    vector<int> tans;
    for(int i=1;i<=n;i++) if(v[i]==1) tans.push_back(i);
    sort(tans.begin(),tans.end(),[](int a,int b)->bool{return tr->v[a].dfn<tr->v[b].dfn;});

    printf("%d\n",(tans.size()+1)/2);
    for(int i=1;i<=tans.size()/2;i++) 
    {
        printf("%d %d\n",tans[i-1],tans[tans.size()/2+i-1+(tans.size()%2)]);
    }
    
    if(tans.size()%2==1) printf("%d %d\n",tans[tans.size()/2],1);
    
    return 0;
}

D.Duration

wrf (00:04:04) +0

题意

给出两个时分秒表示的时间,问相差多少秒

题解

签到题,都化归成秒就可以了

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(void)
{    
    ll h1,m1,s1;
    ll h2,m2,s2;

    scanf("%lld:%lld:%lld",&h1,&m1,&s1);
    scanf("%lld:%lld:%lld",&h2,&m2,&s2);

    ll k1=h1*3600+m1*60+s1;
    ll k2=h2*3600+m2*60+s2;
    printf("%lld",abs(k1-k2));
    
    return 0;
}

E.Exclusive OR

lmj (赛后)

题意:

长度为$n$的数组,求取$1-n$个数(可重复)的异或最大值

题解:

因为数据范围为$2^{18}$,所以在19次之后答案是不变的 $ans[i]=ans[i-2]$,对于前19个答案,考虑采用fwt解决。做的时候用了模1e9+7,实际上是会有可能错误的,刚好该位为1e9+7的倍数,那么就错了,只是不太好构造数据。正确做法为将所有大于1的位置全部置1,因为只需要判断是否存在即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=3e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void FWT(int *a,int n)
{
    for(int d=1;d<n;d<<=1){
        for(int m=d<<1,i=0;i<n;i+=m){
            for(int j=0;j<d;j++){
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=(x+y)%p;
                a[i+j+d]=(x-y+p)%p;
            }
        }
    }
}
ll inv2;
void UFWT(int *a,int n)
{
    for(int d=1;d<n;d<<=1){
        for(int m=d<<1,i=0;i<n;i+=m){
            for(int j=0;j<d;j++){
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=(x+y)%p*inv2%p,a[i+j+d]=(x-y+p)%p*inv2%p;
            }
        }
    }
}
int ans[N];
int a[N];
int b[N];
void work()
{
    inv2=qpow(2,p-2);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        a[x]++;
        b[x]++;
        ans[1]=max(ans[1],x);
    }
    FWT(a,(1<<18));
    for(int i=2;i<=min(20,n);i++){
        FWT(b,(1<<18));
        for(int j=0;j<(1<<18);j++){
            b[j]=1ll*b[j]*a[j]%p;
        }
        UFWT(b,(1<<18));
        for(int j=1<<18;j>=0;j--){
            if(b[j]){
                ans[i]=j;
                break;
            }
        }
    }
    for(int i=21;i<=n;i++){
        ans[i]=ans[i-2];
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Fake Maxpooling

lmj (00:59:05) +1

题意

$n*m$的矩阵中每一位为$gcd(i,j)$,求所有$k*k$的子矩阵中最大值的和

题解

使用单调队列,先将每个位置往下k个中最大值记录下来,然后再$n*m$遍历时以前面求出的答案为基础往右k个中最大值加入答案。$O(n*m)$

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[5005][5005];
int s[5005][5005];
void work()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=i*j/__gcd(i,j);
        }
    }
    ll ans=0;
    paii q[5005];
    int r=0;
    int l=1;
    for(int i=1;i<=m;i++){
        r=0,l=1;
        for(int j=1;j<k;j++){
            while(r>=l&&q[r].fr<a[j][i])r--;
            q[++r].fr=a[j][i];
            q[r].sc=j;
        }
        for(int j=1;j<=n-k+1;j++){
            while(r>=l&&q[r].fr<a[j+k-1][i])r--;
            q[++r].fr=a[j+k-1][i];
            q[r].sc=j+k-1;
            while(q[l].sc<j)l++;
            s[j][i]=q[l].fr;
        }
    }
    for(int i=1;i<=n-k+1;i++){
        r=0;
        l=1;
        for(int j=1;j<k;j++){
            while(r>=l&&q[r].fr<s[i][j])r--;
            q[++r].fr=s[i][j];
            q[r].sc=j;
        }
        for(int j=k;j<=m;j++){
            while(r>=l&&q[r].fr<s[i][j])r--;
            q[++r].fr=s[i][j];
            q[r].sc=j;
            while(q[l].sc<j-k+1)l++;
            ans+=q[l].fr;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    while(T--){
        work();
    }
}

G.Greater and Greater

zyj (赛后) +0

题意

给出两个数组A和B,问你在A中有多少长为m的连续子段满足$ \forall i \in\{1,2, \cdots, m\}, S_{i} \geq B_{i} $
$ (1 \leq n \leq 150000,1 \leq m \leq \min \{n, 40000\}) $

题解

暴力是nm的复杂度,算一下是6e9,再看到这个奇奇怪怪的150000,这不是明摆着告诉你是一道Bitset题了嘛!
我们首先将A和B按照pair序排序,顺便记录一下每个数的pos,然后维护两个bitset ans和now,一个维护答案,另一个维护「在A数组中所有大于等于b[i]的下标」,很显然排序完之后只需要$ O(n+m) $即可维护;
维护完now之后,我们对于B数组中每个数考虑,当前的b[i]对应的合法状态就是目前的now,将now右移b[i].pos位之后也就对应了A数组中合法的状态,将这所有m个合法状态&一下,如果是1就对应一个解;

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define x first
#define y second
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m;
pair<int,int> a[maxn],b[maxn];
bitset<150001> ans,now;
int main(){
    scanf("%d%d",&n,&m);
    rep(i,0,n-1) scanf("%d",&a[i].x),a[i].y=i;
    rep(i,0,m-1) scanf("%d",&b[i].x),b[i].y=i;
    sort(a,a+n);sort(b,b+m);
    ans.set();now.set();
    int pos=0;
    rep(i,0,m-1){
        while(pos<n&&a[pos].x<b[i].x) now[a[pos++].y]=0;
        ans&=now>>b[i].y;
    }int cnt=0;
    rep(i,0,n-m) cnt+=ans[i];
    printf("%d\n",cnt);
}

H.Happy Triangle

lmj (赛后)

题意

三种操作 1 x 把一个x加入multiset 2 x 把一个x从multiset中删除 3 x 在multiset中找2个数使得这三个数能构成三角形。

题解

使用set+map来记录当前哪些数在multiset中,考虑构成三角形,如果x为最长边,那么只要找到刚好等于或者小于x的两个数,判断这两个数的和是否大于x。如果x不为最长边,考虑找最长边比x大的数中,离前一个数差最小的值,这个考虑使用线段树维护和前一个数的差的最小值,离线,将x离散化,在每次删除和加入时对线段树的值进行修改即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
const ll inf=1e11;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
map<int,int>m;
map<int,int>m1;
set<int>s;
int op[N],x[N];
int y[N];
ll sum[N<<2];
void build(int l,int r,int rt)
{
    if(l==r){
        sum[rt]=inf;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);
}
void update(int l,int r,int rt,int x,ll c)
{
    if(l==r){
        sum[rt]=c;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)update(l,mid,rt<<1,x,c);
    else update(mid+1,r,rt<<1|1,x,c);
    sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);
}
ll query(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r){
        return sum[rt];
    }
    int mid=(l+r)>>1;
    if(R<=mid)return query(l,mid,rt<<1,L,R);
    if(L>mid)return query(mid+1,r,rt<<1|1,L,R);
    return min(query(l,mid,rt<<1,L,R),query(mid+1,r,rt<<1|1,L,R));
}
void work()
{
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&op[i],&x[i]);
        y[i]=x[i];
    }
    sort(y+1,y+q+1);
    int tot=unique(y+1,y+q+1)-y-1;
    build(1,tot,1);
    for(int i=1;i<=tot;i++){
        m1[y[i]]=i;
    }
    set<int>::iterator it,it1,it2;
    for(int i=1;i<=q;i++){
        if(op[i]==1){
            m[x[i]]++;
            if(m[x[i]]==1){
                s.insert(x[i]);
                it1=it2=it=s.find(x[i]);
                if(it!=s.begin()){
                    it1--;
                    update(1,tot,1,m1[x[i]],x[i]-(*it1)); 
                }
                it2++;
                if(it2!=s.end()&&m[*it2]==1){
                    update(1,tot,1,m1[*it2],(*it2)-x[i]); 
                }
            }else{
                update(1,tot,1,m1[x[i]],0);
            }
        }
        if(op[i]==2){
            m[x[i]]--;
            if(m[x[i]]==1){
                it=s.find(x[i]);
                if(it!=s.begin()){
                    it--;
                    update(1,tot,1,m1[x[i]],x[i]-(*it));
                }else{
                    update(1,tot,1,m1[x[i]],inf);
                }
            }
            if(m[x[i]]==0){
                it1=it2=it=s.find(x[i]);
                it2++;
                it1--;
                if(it2!=s.end()&&m[*it2]==1){
                    if(it==s.begin()){
                        update(1,tot,1,m1[*it2],inf);
                    }else{
                        update(1,tot,1,m1[*it2],*it2-*it1);
                    }
                }
                update(1,tot,1,m1[x[i]],inf);
                s.erase(x[i]);
            }
        }
        if(op[i]==3){
            it1=it2=it=s.lower_bound(x[i]);
            if(m[x[i]]>=2){
                printf("Yes\n");continue;
            }
            if(m[x[i]]==1&&it!=s.begin()){
                printf("Yes\n");continue;
            }
            if(it!=s.begin()){
                it1--;
                if(m[*it1]>=2){
                    if((*it1)*2>x[i]){
                        printf("Yes\n");continue;
                    }
                }
                int tmp=*it1;
                if(it1!=s.begin()){
                    it1--;
                    tmp+=*it1;
                    if(tmp>x[i]){
                        printf("Yes\n");continue;
                    }
                }
            }
            if(query(1,tot,1,m1[x[i]],tot)<x[i]){
                printf("Yes\n");
            }else{
                //printf("%d %d %lld\n",m1[x[i]],tot,query(1,tot,1,m1[x[i]],tot));
                printf("No\n");
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.Interval

zyj (赛后) +2

题意

给一个初始区间 $[1,n]$ ,每次可以将当前区间 $[l,r]$ 变成 $[l+1,r]$ , $[l-1,r]$ ,$[l,r+1]$ ,$[l,r-1]$ 四种,并且有若干种禁止操作,第 i 个操作表示你可以花 $c_i$ 的代价禁止掉区间为 $[l_i,r_i]$ 时的某个操作(题给方向),问任意时刻区间都不能为 $ [l,r]$ && $l==r $ 的最小代价

题解

读完这道题再看完数据范围之后脑子就告诉我这不裸的最小割嘛(但是场上没人看这题
我们首先考虑以题给的区间建图。一个区间即代表一个点;一个区间(l,r,L,c)向它能一步到达的区间(l+1,r,dir,c)连容量为c的边(如果有这个区间),然后向所有不能一步到达但是包含于当前区间内且是当前区间的一个极大子区间的区间连INF的边,举个例子:三个区间(1,5),(2,4),(3,4),(1,5)可以向(2,4)连边,但是不能向(3,4)连边(因为(2,4)要向(3,4)连边);汇点就是所有(i,i)的区间,跑最小割即是答案;
但是!这样建图点数$O(m)$的,边数可以卡到$m^2$,显然会TLE。其实这样的模型很显然就是网格图,区间[l,r]对应网格中的点(l,r),每个点只能向上下左右四个方向走,如果题给了一个限制条件限制了(l,r)到(l+1,r),那么我们就在网格图中连边(l,r)->(l,r-1)(因为花费了c之后只能走这条路),那么就转换成求最短路了。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const ll INF=(ll)1e18;
int n,m;
struct Edge{
    int v;ll w;int nex;
}g[maxn<<1];
int head[maxn],edge_tot;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(int u,int v,ll w=1){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
void add(int u,int v,ll w){addedge(u,v,w);addedge(v,u,w);}
typedef pair<ll,int> pii;
ll dis[maxn],vis[maxn];
void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    rep(i,0,n*n+10) dis[i]=INF,vis[i]=0; dis[s]=0;
    Q.push({dis[s],s});
    while(!Q.empty()){
        pii tmp=Q.top();Q.pop();
        int x=tmp.second;
        if(vis[x]) continue; vis[x]=1;
        for(int i=head[x];i;i=g[i].nex){
            int v=g[i].v;ll w=g[i].w;
            if(dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                Q.push({dis[v],v});
            }
        }
    }
}
int id[501][501],cnt=0;
int main(){
    scanf("%d%d",&n,&m);init();
    rep(i,1,n) rep(j,1,n) id[i][j]=++cnt;
    int s=++cnt,t=++cnt;
    rep(i,1,n) id[0][i]=s,id[i][n+1]=t;
    rep(i,1,m){
        int l,r,c;char s[3];
        scanf("%d%d%s%d",&l,&r,s,&c);
        if(s[0]=='L') add(id[l][r],id[l][r+1],c);
        else add(id[l][r],id[l-1][r],c);
    }
    dijkstra(s);
    if(dis[t]>=INF) dis[t]=-1;
    printf("%lld\n",dis[t]);
}

J.Just Shuffle

lmj (03:25:46) +3

题意

给一个长度为$n$的$1-n$的排列,开始为$1,2,3,……,n$,给出经过$k$次相同置换后得到的排列,问置换一次后的排列

题解

因为k为质数,所以在置换时循环大小不会变化,所以给定排列的循环大小就是置换的循环大小,对于每一个循环单独考虑,将$k mod len$当做一次置换(注意给出的是置换完的样子,而不是置换),那么只要找到$x*k mod len=1$时的$x$,做$x$次置换,就可以得到答案

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
#define MOD 76543
const int N=2e5+5;
ll qpow(ll a,ll n,ll p){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int b[N];
int vis[N];
int vis1[N];
int c[N];
vector<int>v[N];
void work()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=i;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int x=i;
            tot++;
            while(!vis[x]){
                vis[x]=1;
                c[a[x]]=x;
                x=a[x];
            }
            x=i;
            while(!vis1[x]){
                //printf("%d %d\n",x,c[x]);
                vis1[x]=1;
                v[tot].push_back(x);
                x=c[x];
            }
            int len=v[tot].size();
            ll tmp=k%len;
            ll sum=0;
            ll cnt=0;
            if(len!=1){
                while(sum%len!=1){
                    sum+=tmp;
                    cnt++;
                }
            }
            //printf("%d\n",cnt);
            for(int i=0;i<v[tot].size();i++){
                //printf("%d ",v[tot][i]);
                b[v[tot][(i+cnt)%len]]=v[tot][i];
            }
            //printf("\n");
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",b[i]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.Keyboard Free

lmj (赛后)

题意

给三个同心圆,半径分别为$r_1,r_2,r_3$,点$A,B,C$分别在三个圆上,求三个点形成的三角形的面积的期望

题解

考虑将A设置为定点,然后枚举另外两个点和A的夹角分为500份,然后枚举这250000种情况求出面积,然后求平均值即可

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const double PI=acos(-1);
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
double c[505],s[505];
void work()
{
    int r[4];
    scanf("%d%d%d",&r[1],&r[2],&r[3]);
    sort(r+1,r+4);
    pair<double,double>x1,x2,x3;
    x1.fr=r[1];
    x1.sc=0;
    double ans=0;
    int j;
    double i;
    for(j=0,i=0;i<=2*PI;i+=2*PI/500,j++){
        c[j]=cos(i);
        s[j]=sin(i);
    }
    for(int i=0;i<500;i++){
        x2.fr=c[i]*r[2];
        x2.sc=s[i]*r[2];
        for(int j=0;j<500;j++){
            x3.fr=c[j]*r[3];
            x3.sc=s[j]*r[3];
            ans+=abs((x2.fr-x1.fr)*(x3.sc-x1.sc)+(x2.sc-x1.sc)*(x3.fr-x1.fr));
        }
    }
    printf("%.1f\n",ans/500/500/2);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}
Responses / Cancel Reply
  1. [...]结论题,答案为B^{T}AB,证明[...]

    Reply
  2. Cryle

    太强啦,向大佬们学习!!

    Reply