The 15th Chinese Northeast Collegiate Programming Contest

简介: The 15th Chinese Northeast Collegiate Programming Contest

linkkkkkk

1001 Matrix

题意:

用[ 1 , n 2 ]的数填n ∗ n的矩阵,每个数字只能用一次,记a i表示第i行的最大值

S = a 1 , a 2 , . . . , a n ∩ 1 , 2 , . . . , n . S={a1,a2,...,an}∩{1,2,...,n}.

求∑ ∣ S ∣ \sum|S|∑∣S∣

思路:

考虑每一个数的贡献,比如1可以作为贡献的方案数就是n ∗ C n 2 − 1 n − 1。

其中组合数部分表示1作为该行的最小值出现,选择剩下的数的方案数;n表示该行可以出现在1 − n里任意一行。

最后还要乘n ! ∗ ( n 2 − n ) !。前者表示1所在行的所有数都可以全排列一遍,后者表示剩下的数可以全排列,对1的贡献是不影响的。

累加出1 − n的贡献,直接求或打表O ( 1 )

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 2e7 + 5e6 + 7;
const int mod = 998244353;
ll qpow(ll a, ll b,ll p)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
ll fac[maxn];
void init()
{
    fac[0]  = 1;
    for(int i = 1; i < maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
}
ll infac(ll x)
{
    return qpow(x, mod - 2, mod);
}
ll C(ll n, ll m)
{
    if(n < m) return 0;
    return fac[n] * infac(fac[m]) % mod * infac(fac[n - m]) % mod;
}
void solve()
{
    ll n;
    scanf("%lld",&n);
    ll ans=n*fac[n]%mod*fac[n*n-n]%mod;
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=C(n*n-i,n-1);
        sum=sum%mod;
    }
    printf("%lld\n",ans*sum%mod);
}
int main()
{
    init();
    int t = 1;
    scanf("%d", &t);
    while(t--)
    {
        solve();
    }
    return 0;
}

1003 Vertex Deletion

linkkkk

1004 Lowbit

题意:

两种操作:

1.给区间[ l , r ]的所有数都加l o w b i t ( a i )

2.区间求和

思路:

如果一个区间的数都变成10000(二进制)这种形式,操作1就相当于区间乘法,维护懒标就好了。设一个标记f l a g表示该段区间都是1000这种形式,对于操作1的区间,看是否能转化成区间乘法

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
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;}
inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const double PI=acos(-1.0);
ll ksm(ll a,ll b,ll p){
    ll res=1;
    a%=p;
    while(b){
//&运算当相应位上的数都是1时,该位取1,否则该为0。
        if(b&1)
            res=1ll*res*a%p;//转换为ll型
        a=1ll*a*a%p;
        b>>=1;//十进制下每除10整数位就退一位 
    }
    return res;
}
const int maxn=1e5+100;
const ll mod=998244353;
struct node{
    int l,r,flag;
    ll sum,laz;
}tr[maxn*4];
int n,m;
ll a[maxn];
ll lowbit(ll x){return x&-x;}
void pushup(int u){
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
    tr[u].flag=tr[u<<1].flag&tr[u<<1|1].flag;
}
void pushdown(int u){
    if(tr[u].laz){
        ll t=tr[u].laz;
        tr[u<<1].sum=(tr[u<<1].sum*ksm(2,t,mod))%mod;
        tr[u<<1|1].sum=(tr[u<<1|1].sum*ksm(2,t,mod))%mod;
        tr[u<<1].laz+=t;
        tr[u<<1|1].laz+=t;
        tr[u].laz=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    tr[u].flag=tr[u].laz=tr[u].sum=0;
    if(l==r){
        tr[u].flag=tr[u].laz=0;
        tr[u].sum=a[l];
        if(a[l]==lowbit(a[l])) tr[u].flag=1;
        return ;
    }
    int mid=(l+r)/2;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int ql,int qr){
    if(tr[u].flag&&l>=ql&&r<=qr){
        tr[u].laz++;
        tr[u].sum=(tr[u].sum*2)%mod;
        return ;
    }
    if(l==r){
        ll tmp=lowbit(a[l]);
        a[l]+=tmp;
        tr[u].sum+=tmp;
        if(tr[u].sum==lowbit(tr[u].sum)){
            tr[u].flag=1;
        }
        return ;
    }
    pushdown(u);
    int mid=(l+r)/2;
    if(ql<=mid) update(u<<1,l,mid,ql,qr);
    if(qr>mid) update(u<<1|1,mid+1,r,ql,qr);
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
    tr[u].flag=tr[u<<1].flag&tr[u<<1|1].flag;
}
ll query(int u,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr){return tr[u].sum;}
    pushdown(u);
    ll ans=0;
    int mid=(l+r)/2;
    if(ql<=mid) ans=(ans+query(u<<1,l,mid,ql,qr))%mod;
    if(qr>mid) ans=(ans+query(u<<1|1,mid+1,r,ql,qr))%mod;
    return ans;
}
int main(){
    int _;cin>>_;
    while(_--){
        n=read;
        rep(i,1,n) a[i]=read;
        build(1,1,n);
        m=read;
        while(m--){
            int op=read,l=read,r=read;
            if(op==1) update(1,1,n,l,r);
            else printf("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}

1005 Easy Math Problem

思维构造

int main()
{
    int t=1;
    scanf("%d",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        cout<<6*n<<" "<<3<<endl;
        cout<<n<<" "<<2*n<<" "<<3*n<<endl;
    }
    return 0;
}

1009 Takeaway

阅读理解题

int a[]={0,7,27,41,49,63,78,108};
int main(){
    closeSync;
    int _=read;
    while(_--){
        int n=read,sum=0;
        rep(i,1,n){
            int x=read;
            sum+=a[x];
        }
        int ans=0;
        if(sum>=120) ans+=50;
        if(sum<120&&sum>=89) ans+=30;
        if(sum<89&&sum>=69) ans+=15;
        cout<<sum-ans<<endl;
    }
    return 0;
}

1010 Transform

题意:

三维空间里给出一个点和一个向量,问点围绕向量旋转t度后,输出z坐标大的点

思路:

板子题

代码:

const double PI=acos(-1.0);
//定义返回结构体
struct Point3f
{
    Point3f(double _x, double _y, double _z)
    {
        x = _x;
        y = _y;
        z = _z;
    }
    double x;
    double y;
    double z;
};
Point3f cul(double old_x, double old_y, double old_z, double vx, double vy, double vz, double theta)
{
    double r = theta * PI / 180;
    double c = cos(r);
    double s = sin(r);
    double new_x = (vx*vx*(1 - c) + c) * old_x + (vx*vy*(1 - c) - vz*s) * old_y + (vx*vz*(1 - c) + vy*s) * old_z;
    double new_y = (vy*vx*(1 - c) + vz*s) * old_x + (vy*vy*(1 - c) + c) * old_y + (vy*vz*(1 - c) - vx*s) * old_z;
    double new_z = (vx*vz*(1 - c) - vy*s) * old_x + (vy*vz*(1 - c) + vx*s) * old_y + (vz*vz*(1 - c) + c) * old_z;
    return Point3f(new_x, new_y, new_z);
}
int main(){
    int _=read;
    while(_--){
        double x1,y1,z1,x2,y2,z2,t;
        cin>>x1>>y1>>z1>>x2>>y2>>z2>>t;
        double sum=sqrt(x1*x1+y1*y1+z1*z1);
        x1/=sum,y1/=sum,z1/=sum;
        Point3f t1=cul(x2,y2,z2,x1,y1,z1,t);
        Point3f t2=cul(x2,y2,z2,x1,y1,z1,-1*t);
        if(t1.z>t2.z) printf("%.6f %.6f %.6f\n",t1.x,t1.y,t1.z);
        else printf("%.6f %.6f %.6f\n",t2.x,t2.y,t2.z);
    }
    return 0;
}

1011 City

题意:

给出一个图,每次询问给出x,每次将边权< x

思路:

按照边权从大到小排序,依次连边,每次连边产生的贡献是s i z [ u ] ∗ s i z [ v ]

代码:

const int maxn=2e5+10,inf=0x3f3f3f3f;
const double eps=1e-5;
int n,m,q;
struct node{
    int u,v,w;
}edge[maxn];
bool cmp(node a,node b){
    return a.w>b.w;
}
struct ask{
    int id,w;
}qask[maxn];
bool cmp1(ask a,ask b){
    return a.w>b.w;
}
ll root[maxn],siz[maxn],ans[maxn];
int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}
int main(){
    closeSync;
    int _;cin>>_;
    while(_--){
        cin>>n>>m>>q;
        rep(i,1,m){
            cin>>edge[i].u>>edge[i].v>>edge[i].w;
        }
        sort(edge+1,edge+1+m,cmp);
        rep(i,1,n) root[i]=i,siz[i]=1;
        rep(i,1,q){
            cin>>qask[i].w;qask[i].id=i;
        }
        sort(qask+1,qask+1+q,cmp1);
        ll now=1,sum=0;
        for(int i=1;i<=q;i++){
            while(edge[now].w>=qask[i].w){
                int u=edge[now].u,v=edge[now].v;
                int fu=Find(u),fv=Find(v);
                if(fu!=fv){
                    sum+=siz[fu]*siz[fv];
                    root[fu]=fv;
                    siz[fv]+=siz[fu];
                }
                now++;
            }
            ans[qask[i].id]=sum;
        }
        rep(i,1,q) cout<<ans[i]<<endl;
    }
    return 0;
}

1013 Master of Shuangpin

思路:

模拟。

代码:

const int maxn=500005,inf=0x3f3f3f3f;
const double eps=1e-5;
map<string,string>mp;
void init(){
    mp["q"] = "q";
    mp["iu"] = "q";
    mp["w"] = "w";
    mp["ei"] = "w";
    mp["e"] = "e";
    mp["r"] = "r";
    mp["uan"] = "r";
    mp["t"] = "t";
    mp["ue"] ="t";
    mp["y"] = "y";
    mp["un"] = "y";//
    mp["u"] = "u";
    mp["sh"] = "u";
    mp["i"] = "i";
    mp["ch"] = "i";
    mp["o"] = "o";
    mp["uo"] = "o";
    mp["p"] = "p";
    mp["ie"] = "p";
    mp["a"] ="a";
    mp["s"] = "s";
    mp["ong"] = "s";
    mp["iong"] = "s";
    mp["d"] = "d";
    mp["ai"] = "d";
    mp["f"] = "f";
    mp["en"] = "f";
    mp["g"] = "g";
    mp["eng"] = "g";
    mp["h"] = "h";
    mp["ang"] = "h";
    mp["j"] = "j";
    mp["an"] = "j";
    mp["k"] = "k";
    mp["uai"] = "k";
    mp["ing"] = "k";
    mp["l"] = "l";
    mp["uang"] = "l";
    mp["iang"] = "l";
    mp["z"] = "z";
    mp["ou"] = "z";
    mp["x"] = "x";
    mp["ia"] = "x";
    mp["ua"] = "x";
    mp["c"] = "c";
    mp["ao"] = "c";
    mp["v"] = "v";
    mp["ui"] = "v";
    mp["zh"] = "v";
    mp["b"] = "b";
    mp["in"] = "b";
    mp["n"] = "n";
    mp["iao"] = "n";
    mp["m"] = "m";
    mp["ian"] = "m";
}
int main(){
    init();
    string s;
    while(getline(cin,s)){
        stringstream ss;
        ss<<s;
        string tt="";
        while(ss>>s){
            if(s.size()==1) tt=tt+s+s+" ";//cout<<s<<s<<" ";
            else if(s.size()==2) tt=tt+s+" ";//cout<<s<<" ";
            else{
                if(mp.count(s)){
                    tt=tt+s[0]+mp[s]+" ";
//                    cout<<s[0]<<mp[s]<<" ";
                    continue;
                }
                string res="";
                bool flag=0;
                for(int i=1;i<s.size();i++){
                    string s1=s.substr(0,i);
                    string s2=s.substr(i,s.size()-1);
                    //cout<<s1<<" "<<s2<<endl;
                    if(mp.count(s1)&&mp.count(s2)){
                        flag=1;
                        res=mp[s1]+mp[s2];
                        break;
                    }
                }
                tt=tt+res+" ";
//                cout<<res<<" ";
            }
        }
        tt=tt.substr(0,tt.size()-1);
        cout<<tt<<endl;
    }
    return 0;
}




目录
相关文章
The Preliminary Contest for ICPC China Nanchang National Invitational M题 Subsequence
The Preliminary Contest for ICPC China Nanchang National Invitational M题 Subsequence
74 0
The Preliminary Contest for ICPC China Nanchang National Invitational A题 PERFECT NUMBER PROBLEM
The Preliminary Contest for ICPC China Nanchang National Invitational A题 PERFECT NUMBER PROBLEM
70 0
The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)
The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)
111 0
|
人工智能
Nordic Collegiate Programming Contest 2020 D.Damsindistress (dp)
Nordic Collegiate Programming Contest 2020 D.Damsindistress (dp)
94 0
|
定位技术
German collegiate programming contest 2012 - Ski Jumping
首先用动能定理算出平抛的初速度v0,然后分三种情况,0~L/2,L/2~L,L~无穷远。
135 0
German collegiate programming contest 2012 - Ski Jumping