头像

第一万零一次AC

EPI SOFTWARE LAB




离线:33分钟前


最近来访(76)
用户头像
青衣程碟衣
用户头像
johnwhite
用户头像
XiangxinZhong
用户头像
CHEN11
用户头像
Makisekurisu_4
用户头像
Froggy
用户头像
有点大的青椒
用户头像
NGC2237_7
用户头像
桑晚
用户头像
Albert_7
用户头像
心向远方
用户头像
rarestark
用户头像
13569840960
用户头像
daftchris
用户头像
禾小青
用户头像
下界合金镐
用户头像
江苏余政恩
用户头像
少年补题王
用户头像
余火
用户头像
好温柔

活动打卡代码 AcWing 1875. 贝茜的报复

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 150;
typedef long long LL;
unordered_map<char,vector<int>>S;

int n,x;
char c;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>c>>x;
        S[c].push_back(x);
    }
    LL t1=0,t2=0,t3=0;
    for(int b=0;b<S['B'].size();b++) //算出B+I为奇数的方案数
    {
        for(int i=0;i<S['I'].size();i++)
        {
            if((S['B'][b] + S['I'][i])%2) t1++;
        }
    }
    for(int g=0;g<S['G'].size();g++)//算出G+O+E+S的方案数
    {
        for(int o=0;o<S['O'].size();o++)
        {
            for(int e=0;e<S['E'].size();e++)
            {
                for(int s=0;s<S['S'].size();s++)
                {
                    if((S['G'][g] + S['O'][o] + S['E'][e] + S['S'][s])%2) t2++;
                }
            }
        }
    }
    for(int m=0;m<S['M'].size();m++) if(S['M'][m]%2) t3++;//算出M为奇数的方案数
    LL sum = 1;
    for(auto x:S) sum = (LL)sum * x.second.size();//算出总方案数
    cout<<sum - t1*t2*t3<<endl;//由于各个方案中字母是互斥的,根据容斥原理及奇x奇=奇得答案 = 总方案数 - 三者均为奇数的方案数
    return 0;
}


活动打卡代码 AcWing 1929. 镜子田地

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

char g[N][N];
int n,m;
int ans = -1;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dfs(int x,int y,int d)
{
    if(x<0||x>=n||y<0||y>=m) return 0;

    if(g[x][y] == '\\')  
    {
        d = 3 - d; 
    }
    else d = d ^ 1;
    return dfs(x + dx[d],y + dy[d],d) + 1;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>g[i];
    }
    for(int i=0;i<n;i++)
    {
        ans = max(ans,dfs(i,0,1));//从左边射入
        ans = max(ans,dfs(i,m-1,3));//从右边射入
    }
    for(int i=0;i<m;i++)
    {
        ans = max(ans,dfs(0,i,2));//从上边射入
        ans = max(ans,dfs(n-1,i,0));//从下边射入
    }

    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1212. 地宫取宝

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55,MOD = 1000000007;

int n,m,k;
int w[N][N];
int f[N][N][13][14];//状态表示:横坐标,纵坐标,已经取了多少件,当前价值

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&w[i][j]);
            ++w[i][j];//由于起初要遍历(1,1),C++数组下标不支持-1,故映射价值到[1,13]
        }
    }
    f[1][1][0][0] = 1;
    f[1][1][1][w[1][1]] = 1;
    for(int i=1;i<=n;i++)//枚举横坐标
    {
        for(int j=1;j<=m;j++)//枚举纵坐标
        {
            if(i==1 && j==1) continue;//(1,1)处已经处理过了
            for(int u=0;u<=k;u++)//枚举已经取的个数,不大于k
            {
                for(int v=0;v<=13;v++)//枚举当前价值
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i-1][j][u][v]) % MOD;//价值小于当前宝物价值,不选
                    val = (val + f[i][j-1][u][v]) % MOD;//出于范围的考虑,最多加2数就取模
                    if(u > 0 && v == w[i][j])
                    {
                        for(int c=0;c<v;c++)
                        {
                            val = (val + f[i-1][j][u-1][c]) % MOD;//价值等于当前宝物价值,选
                            val = (val + f[i][j-1][u-1][c]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<=13;i++) ans = (ans + f[n][m][k][i]) % MOD;
    cout<<ans<<endl;
    return 0;
}



#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 1005;
int n,a[N],ans;
int f[N];//状态表示:所有以i结尾的严格单调上升子序列的集合
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i] = 1;//初始化,最短子序列为1
    }
   for(int i=2;i<=n;i++)//右端点
   {
       for(int j = 1;j<=i;j++)
       {
           if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);//如果a[i]左边有比它小的数,选取个数较多的集合
           ans = max(ans,f[i]);//结果方案不一定包含最后一个数,因此需要取最大值
       }
   }
   cout<<ans<<endl;
   return 0;
}



#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 1005;
int n,a[N],ans;
int f[N];//所有以i结尾的严格单调上升子序列的集合
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i] = 1;//初始化,最短子序列为1
    }
   for(int i=2;i<=n;i++)//右端点
   {
       for(int j = 1;j<=i;j++)
       {
           if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);//如果a[i]左边有比它小的数,选取个数较多的集合
           ans = max(ans,f[i]);//结果方案不一定包含最后一个数,因此需要取最大值
       }
   }
   cout<<ans<<endl;
   return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include<iostream>
using namespace std;

const int N = 105;
int f[N][N],g[N][N]; //f[i][j]:状态表示第i行第j列取得花生数最大值
int T,m,n,x;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);//n行m列
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&g[i][j]);
            }
        }

        //f[1][1] = g[1][1];//区域外方案数为0,无需初始化
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j] = max(f[i-1][j] + g[i][j],f[i][j-1] + g[i][j]);//来自上方和左边的方案数加上当前花生数,求较大者
            }
        }
        cout<<f[n][m]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

#include<iostream>
using namespace std;

const int M = 1005;
int n,m;//物品数量和背包体积
int v[M],w[M];//表示某件物品的体积和价值
int f[M][M];//状态表示:包含所有选法的集合

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    //f[0][0~M]全部初始化为0
    for(int i=1;i<=n;i++) //枚举前i件物品
    {
        for(int j=1;j<=m;j++)//枚举不超过j的体积
        {
            if(v[i] > j) f[i][j] = f[i-1][j];//当前背包容量装不进第i个物品,则价值等于前i-1个物品
            else f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//能装,需进行决策是否选择第i个物品
        }
    }
    cout<<f[n][m]<<endl;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

#include<iostream>
#include<stack>
using namespace std;

const int N = 1e5+10;

int n,x,v;
stack<int>stk;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x,&v);//数据按位置前后顺序
        while(!stk.empty() && v < stk.top()) stk.pop();//将此牛后面速度较大的所有牛都除去,即栈中大于栈顶的元素都出栈
        stk.push(v);//所有牛先入栈
    }
    cout<<stk.size()<<endl;//栈中的牛都不会发生相遇,将他们单独成组,因此栈中元素个数就是组数
    return 0;
}


活动打卡代码 AcWing 1913. 公平摄影

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1e5+10;
#define x first
#define y second

typedef pair<int,int>PII;

int n;
PII q[N];//奶牛的信息
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        char str[2];
        scanf("%d%s",&x,str);
        if(*str == 'G') q[i] = {x,1};
        else q[i] = {x,-1};
    }

    sort(q+1,q+n+1);
    unordered_map<int,int>hash; //键记录前缀和,值记录下标
    int last = 1,ans = 0,sum = 0;
    for(int i=1;i<=n;i++)
    {
        if(!hash.count(sum)) hash[sum] = q[i].x;//当前sum不存在,记录sum值及下标
        sum += q[i].y;//计算前缀和
        if(hash.count(sum)) ans = max(ans,q[i].x - hash[sum]);//若之前存在区间与前缀和相等,他们相减就是奶牛均衡的区间,求最大区间

        //计算同类奶牛连续的情况
        if(i == 1 || q[i].y != q[i-1].y)//相邻种类不同则更新last
        {
            last = q[i].x; 
        }
        ans = max(ans,q[i].x - last); //个数就是端点之差加1,次数的i已经是右端点的下一位
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1922. 懒惰的牛

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;

int n,k,g,x;
LL s[N],ans,sum;
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&g,&x);
        s[x+1] += g;//题目中x在0—1e6,为了方便计算前缀和,将其映射到1~1e6+1
    }
    for(int i=1;i<=1e6+1;i++)
    {
        s[i] += s[i-1];//计算前缀和
    }
    for(int i=1;i<=1e6+1;i++)
    {
        int l = max(1,i-k);//左端点
        int r = min(1000001,i+k);//右端点
        sum = s[r] - s[l-1];//前缀和算区间和
        //cout<<sum<<endx;
        ans = max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}