高一普及组模拟赛4-2022/5/24

A. The Prices

B. 上白泽慧音

C. 最大公约数和最小公倍数问题

赛时得分：300 / 300（AK力！QWQ）

赛时排行：Rank1（显然

习惯自然是先开T1，但是这个T3他好像莫名有点熟悉……

一看：有点眼熟但想不出来是啥了

（后来赛后看是洛谷P1029）

C. 最大公约数和最小公倍数问题

 这个……没有什么难度吧

只要知道 gcd(x,y)*lcm(x,y)=x*y 就好了啊？

然后我们可以枚举 x

如果可以整除 gcd(x,y)*lcm(x,y) 就判一下最大公约数

完事走人，但后来发现没开long long（事后证明不用）痛失一血

15min写完了

主函数名：Eafoo（Eafoo实在是太可爱了ovo

#include
#include
#include<string>
#include
#define WR WinterRain
#define int long long
#define Eafoo signed
using namespace std;
int x,y;
int ans=0;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
Eafoo main(){
    freopen("gcdpro.in","r",stdin);
    freopen("gcdpro.out","w",stdout);
    x=read(),y=read();
    for(int i=x;i){
        if((x*y)%i==0&&gcd(i,(x*y)/i)==x) ans++;
    }
    ans*=2;
    if(x==y) ans++;
    printf("%lld",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

然后看了眼T1

？？？状压是什么鬼东西？？？

光速逃离开T2

B. 上白泽慧音

 额……

略作思考

Tarjan

又因为目前在做树链剖分所以树上的东西熟的一批

 飞快地写出来了

//好家伙我刚写完树链剖分来了道tarjan
//瞌睡了就来送枕头？QWQ
#include
#include
#include<string>
#include
#define WR WinterRain
#define int long long
#define Sakura signed
using namespace std;
const int WR=5001000;
struct Edge{
    int pre,to;
}edge[WR];
int m,n;
int maxx[WR],sum;
int head[WR],tot;
int ipt[WR],low[WR],dpt[WR],cnt;
int sze[WR],point,id[WR],num;
bool instk[WR],vis[WR];
stack<int>s;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void add(int u,int v){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void tarjan(int u){
    ipt[u]=++cnt,low[u]=ipt[u];
    instk[u]=true,s.push(u);
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(!ipt[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(instk[v]){
            low[u]=min(low[u],ipt[v]);
        }
    }
    if(low[u]==ipt[u]){
        int v;
        point++;
        do{
            v=s.top(),s.pop();
            id[v]=point;
            sze[point]++;
            instk[v]=false;
        }while(u!=v);
    }
}
Sakura main(){
    freopen("classroom.in","r",stdin);
    freopen("classroom.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),opt=read();
        if(opt==1) add(u,v);
        else{add(u,v);add(v,u);}
    }
    for(int i=1;i<=n;i++) if(!ipt[i]) tarjan(i);
    int mx=0,tag;
    for(int i=1;i<=point;i++){
        if(mxi;
    }
    printf("%lld\n",sze[tag]);
    for(int i=1;i<=n;i++){
        if(id[i]==tag) printf("%lld ",i);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

但！是！

我没有判断字典序！！！然后数据太水了居然让我过了……

………………

但这是坏的，所以告诉了虎哥申请加强数据

正解就显然了

主函数名Sakura，Sakura大佬太强了把我吊着打%%%

//好家伙我刚写完树链剖分来了道tarjan
//瞌睡了就来送枕头？QWQ
#include
#include
#include<string>
#include
#define WR WinterRain
#define int long long
#define Sakura signed
using namespace std;
const int WR=5001000;
struct Edge{
    int pre,to;
}edge[WR];
int m,n;
int maxx[WR],sum;
int head[WR],tot;
int ipt[WR],low[WR],dpt[WR],cnt;
int sze[WR],point,id[WR],num;
bool instk[WR],vis[WR];
stack<int>s;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void add(int u,int v){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void tarjan(int u){
    ipt[u]=++cnt,low[u]=ipt[u];
    instk[u]=true,s.push(u);
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(!ipt[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(instk[v]){
            low[u]=min(low[u],ipt[v]);
        }
    }
    if(low[u]==ipt[u]){
        int v;
        point++;
        do{
            v=s.top(),s.pop();
            id[v]=point;
            sze[point]++;
            instk[v]=false;
        }while(u!=v);
    }
}
Sakura main(){
    freopen("classroom.in","r",stdin);
    freopen("classroom.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),opt=read();
        if(opt==1) add(u,v);
        else{add(u,v);add(v,u);}
    }
    for(int i=1;i<=n;i++) if(!ipt[i]) tarjan(i);
    int mx=0,tag;
    for(int i=1;i<=point;i++){
        if(mxsze[i];
    }
    printf("%lld\n",mx);
    for(int i=1;i<=n;i++){
        if(sze[id[i]]==mx){tag=id[i];break;}
    }
    for(int i=1;i<=n;i++){
        if(id[i]==tag) printf("%lld ",i);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

然后只能开T1了……

A. The Prices

 第一眼：这个m怎么这么小？

你好状压

然后推柿子，写了半天出不来

燥热难耐（？）于是滚去上厕所，拿着纸和笔在四楼写写写

然后就推出来了……好像还挺一眼的

首先我们设第一维是在哪一个商店，第二维是状态

空间是100 × 65536 不会炸

然后跑三层循环

第一层 i 枚举在哪一个商店

在循环里首先跑一边所有状态 dp[i][s] = dp[i-1][s] + d[i]

不管我选不选我先到这个商店再说

然后跑第二层循环 s 从 0 到 (1<

对于每一个状态跑一遍物品循环 j ，发现显然的有

dp[i][s|(1<<(j-1))]=min(dp[i][s|(1<<(j-1))] , dp[i][s] + c[i][j])

这个方程的意思是，对于目前状态，有一些已经选择的物品，有一些可选物品

我们判断一下是否值得购买，对于没有买的某个物品我们用当前状态加上选择这个物品的代价判断是否更新

最后再看一遍如果不到这个商店都可以更优那么就搞一个min 完事

主函数名用了SweetHeart，甜鑫大佬太强了%%%

#include
#include
#include<string>
#define WR WinterRain
#define Sweetheart signed
#define int long long
using namespace std;
const int WR=110,INF=2147483647;
int m,n;
int d[WR],c[WR][WR];
int dp[WR][WR*WR*10];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
Sweetheart main(){
    freopen("prices.in","r",stdin);
    freopen("prices.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        d[i]=read();
        for(int j=1;j<=m;j++) c[i][j]=read();
    }
    for(int i=1;i<=(1<1;i++) dp[0][i]=INF;
    for(int i=1;i<=n;i++){//第一维表示在哪一个店铺
        for(int s=0;s<=(1<1;s++){
            dp[i][s]=dp[i-1][s]+d[i];
        }
        for(int s=0;s<=(1<1;s++){
            for(int j=1;j<=m;j++){
                if(!(s&(1<<(j-1)))) dp[i][s|(1<<(j-1))]=min(dp[i][s|(1<<(j-1))],dp[i][s]+c[i][j]);
            }
        }
        for(int s=0;s<=(1<1;s++){
            dp[i][s]=min(dp[i][s],dp[i-1][s]);//我可以一个都不买啊喂
        }
    }
    printf("%lld",dp[n][(1<1]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

今后也要继续努力！OWO