头像

Pr




离线:3小时前



Pr
1天前
#include<iostream>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string m[13]={"0","Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
int main()
{
    string s;
    cin>>s;
    map<string,int> mp;
    for(int i=1;i<=12;i++) mp[m[i]]=i;
    string a=s.substr(0,3);
    string b=s.substr(3);
    cout<<mp[a]<<" "<<atoi(b.c_str())<<"\n";
    return 0;
}



Pr
1天前

思路分析:

  1. 首先这道题需要知道的性质:
  2. 性质1:对于两个数a,b,由a,b凑出的数c=ax+by满足c=k*gcd(a,b),这个性质可以推广到n个数;
  3. 由1得,如果n个数的gcd!=1,说明在无穷个数,只有部分倍数能凑出,所以答案为INF;
  4. 性质2:如果两个数a,b互质,则a,b不能凑出的最大的数为a*b-a-b;(暂且不会证明,太菜了)
  5. 100内,最大的两个互质的数为100和99,这两个数字不能凑出的上界为100*99-100-99,当数字更多的时候,这个上界必然更小可选的数字变多了
  6. 然后这是一道典型的完全背包,每个物品无穷多个,按照常规的线性Dp分析:
    由上面两条性质,结合这道题的DP思路,${\color{Red}f[i][j] }$表示只考虑前i个数,能否凑出j;
    状态转移:${\color{Red} f[i][j]|=f[i-1][j-a[i]k] }$,k表示a[i]选择的次数,满足${\color{Red} j-a[i]k>=0;}$
    注意:f[0][0]=true;
    得到暴力写法:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=10000;
bool f[N][M];
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int p=a[1];
    for(int i=2;i<=n;i++) p=__gcd(p,a[i]);
    if(p!=1) cout<<"INF"<<"\n";
    else{
        f[0][0]=true;
        for(int i=1;i<=n;i++){
           // f[i][a[i]]=true;
            for(int j=0;j<=M;j++){
                for(int k=0;k*a[i]<=j;k++){
                    f[i][j]=f[i][j]||f[i-1][j-k*a[i]];
                }
            }
        }
        int res=0;
        for(int i=0;i<=M;i++){
            if(!f[n][i]) res++;
        }
        cout<<res<<"\n";
    }
    return 0;
}

优化写法:
优化:出现状态重叠
${\color{Red}:f[i][j-a[i]]}是由 {\color{red} f[i-1][j-a[i]],f[i-1][j-a[i]].....f[i-1][j-a[i]*k]}$
所以 $f[i][j]=f[i-1][j]||f[i][j-a[i]]$,同层转移,优化为一维,f[j]|=f[j-a[i]],从小到大枚举

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=10000;
bool f[M];
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int p=a[1];
    for(int i=2;i<=n;i++) p=__gcd(p,a[i]);
    if(p!=1) cout<<"INF"<<"\n";
    else{
        f[0]=true;
        for(int i=1;i<=n;i++){
             f[a[i]]=true;
            for(int j=a[i];j<=M;j++){
                f[j]|=f[j-a[i]];
            }
        }
        int res=0;
        for(int i=0;i<=M;i++){
            if(!f[i]) res++;
        }
        cout<<res<<"\n";
    }
    return 0;
}


活动打卡代码 AcWing 1064. 小国王

Pr
4天前
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=12,M=1<<N;
int n,k;
vector<int> st;
vector<int> head[M];
ll f[N][N*N][M];// 注意爆掉 long long
int cnt[M];
bool check(int x)
{
    for(int i=0;i+1<n;i++){
        if((x>>i &1)&&(x>>(i+1)&1)) return false;
    }
    return true;
}
int count(int x)
{
    int res=0;
    for(int i=0;i<n;i++){
        if(x>>i&1) res++;
    }
    return res;
}
bool vaild(int a,int b)
{
    int c=a|b;
    if(check(c)&&(a&b)==0) return true;
    else return false;
}
void init()
{
    for(int i=0;i<1<<n;i++){
        if(check(i)){
            st.push_back(i);
            cnt[i]=count(i);
        }
    }
    //为了防止tle
    for(int i=0;i<st.size();i++){
        for(int j=0;j<st.size();j++){
            int a=st[i],b=st[j];
            if(vaild(a,b)){
                head[a].push_back(b);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    init();
    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<=k;j++){
            for(int s=0;s<st.size();s++){
               int a=st[s];
               for(int u=0;u<head[a].size();u++){
                int b=head[a][u];
                if(j>=cnt[a])
                f[i][j][a]+=f[i-1][j-cnt[a]][b];
               }
            }
        }
    }
    cout<<f[n+1][k][0]<<endl;
    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

Pr
5天前
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+10;
int q[N];
int main()
{
    int t;
    cin>>t;
    int hh=0,tt=0;
    while(t--){
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[tt++] = x;
        }
        else if (op == "pop") hh ++ ;
        else if (op == "empty") cout << (hh <tt ? "NO" : "YES") << endl;
        else cout << q[hh] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

Pr
5天前
#include<iostream>
#include<cstring>
const int N=3e4+10;
int p[N];
int d[N];//d数组维护同一个集合中到根节点的距离
int cnt[N];
using namespace std;
//再写find函数的时候最重要的就是维护好d[x],因为这里涉及到路径压缩
int find(int x)
{
    if(x==p[x]) return x;
    else{
        //d只维护x到当前根节点的的距离,路径压缩的话
        int r=p[x];//当前的到根节点
        int fa=find(p[x]);//应该合并的节点
        d[x]+=d[r];
        p[x]=fa;
        return p[x];
    }
}
int main()
{
    for(int i=1;i<=N;i++){
        p[i]=i;
        cnt[i]=1;
    } 
    int t;
    scanf("%d",&t);
    while(t--){
        char op;
        int a,b;
        scanf(" %c%d%d",&op,&a,&b);
        if(op=='M'){
             int pa=find(a),pb=find(b);
             p[pa]=pb;
             d[pa]=cnt[pb];
             cnt[pb]+=cnt[pa];
        }
        else{
            int pa=find(a),pb=find(b);
            if(pa!=pb) printf("-1\n");
            else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

Pr
5天前

include[HTML_REMOVED]

include[HTML_REMOVED]

const int N=3e4+10;
int p[N];
int d[N];//d数组维护同一个集合中到根节点的距离
int cnt[N];
using namespace std;
//再写find函数的时候最重要的就是维护好d[x],因为这里涉及到路径压缩
int find(int x)
{
if(x==p[x]) return x;
else{
//d只维护x到当前根节点的的距离,路径压缩的话
int r=p[x];//当前的到根节点
int fa=find(p[x]);//应该合并的节点
d[x]+=d[r];
p[x]=fa;
return p[x];
}
}
int main()
{
for(int i=1;i<=N;i++){
p[i]=i;
cnt[i]=1;
}
int t;
scanf(“%d”,&t);
while(t–){
char op;
int a,b;
scanf(” %c%d%d”,&op,&a,&b);
if(op==’M’){
int pa=find(a),pb=find(b);
p[pa]=pb;
d[pa]=cnt[pb];
cnt[pb]+=cnt[pa];
}
else{
int pa=find(a),pb=find(b);
if(pa!=pb) printf(“-1\n”);
else printf(“%d\n”, max(0, abs(d[a] - d[b]) - 1));
}
}
return 0;
}




Pr
6天前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int p[N];
int cnt[N];
int n,m;
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
         p[i]=i;
         cnt[i]=1;
    }
    while(m--){
        string op;
        int a,b;
        cin>>op;
        if(op=="C"){
            cin>>a>>b;
            int pa=find(a),pb=find(b);
            if(pa!=pb){
                 p[pa]=pb;
                 cnt[pb]+=cnt[pa];
            }
        }
        else if(op=="Q1"){
             cin>>a>>b;
             int pa=find(a),pb=find(b);
             if(pa==pb) cout<<"Yes"<<endl;
             else cout<<"No"<<endl;
        }
        else{
            cin>>a;
            int pa=find(a);
            cout<<cnt[pa]<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1170. 排队布局

Pr
8天前
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010,M=2e6+2*N+10,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
bool st[N];
int dist[N],cnt[N],q[N];
int n,l,d;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool spfa(int len)
{
    memset(dist,0x3f,sizeof(dist));
    memset(st,0,sizeof(st));
    memset(cnt,0,sizeof(cnt));
    int hh=0,tt=0;
    for(int i=1;i<=len;i++){
        q[tt++]=i;
        dist[i]=0;
        st[i]=true;
    }
    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d%d",&n,&l,&d);
    init();
    for(int i=1;i<n;i++) add(i+1,i,0);
    while(l--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a>b) swap(a,b);
        add(a,b,c);
    }
    while(d--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a>b) swap(a,b);
        add(b,a,-c);
    }
    if(spfa(n)){
        printf("-1\n");
    }
    else{
        spfa(1);
        if(dist[n]==INF) printf("-2\n");
        else printf("%d\n",dist[n]);
    }
    return 0;
}


活动打卡代码 AcWing 362. 区间

Pr
8天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
const int N=50010,M=N*3;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
int q[N];
bool st[N];
int n;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa()
{
    memset(dist,-0x3f,sizeof(dist));

    int hh=0,tt=1;
    q[0]=1;
    st[1]=true;
    dist[1]=0;
    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]<dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q[tt++]=j;
                    if(tt==N) tt=0;
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<N;i++) add(i-1,i,0),add(i,i-1,-1);
    while(n--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        add(a-1,b,c);
    }
    spfa();
    printf("%d\n",dist[50001]);
    return 0;
}


活动打卡代码 AcWing 1169. 糖果

Pr
8天前

//最小值求最长路

#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=3e5+10;
int h[N],e[M],ne[M],w[M],idx;
ll dist[N];
bool st[N];
int cnt[N];//用来判断环
int q[N];//队列或者栈的模拟
int n,k;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool spfa()
{
    memset(dist,-0x3f,sizeof(dist));
    q[0]=0;
    dist[0]=0;
    st[0]=true;
    int hh=0,tt=1;
    while(hh!=tt){
        int t=q[--tt];
        //if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]<dist[t]+w[i]){

                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;

                if(cnt[j]>=n+1) return false;
                if(!st[j]){
                    q[tt++]=j;
                    //if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&k);
    init();
    while(k--){
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1) add(a,b,0),add(b,a,0);
        else if(op==2) add(a,b,1);
        else if(op==3) add(b,a,0);
        else if(op==4) add(b,a,1);
        else if(op==5) add(a,b,0);
    }
    //建立超级源点
    for(int i=1;i<=n;i++) add(0,i,1);

    if(!spfa()) printf("-1\n");
    else{
        ll res=0;
        for(int i=1;i<=n;i++) res+=dist[i];
        printf("%lld\n",res);
    }
    return 0;
}