2022牛客寒假算法基础集训营1----ABCDGIK_随笔

2022牛客寒假算法基础集训营1----ABCDGIK 比赛链接 A.九小时九个人九扇门----01背包变形dp
有用的结论：一个数的数字根等于这个数对9取模的结果（特别地，取模得 0则数字根为9）
官方题解：
#include 
using namespace std;
const int N = 100010,mod=998244353;
int f[N][15];
signed main()
{
	int n;cin>>n;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        for(int j=0;j<9;j++)
        {
            (f[i][j]+=f[i-1][j])%=mod;
            (f[i][(j+x)%9]+=f[i-1][j])%=mod;
        }
    }
    (f[n][0]+=mod-1)%=mod;
    for(int i=1;i<=9;i++)cout< 
B.炸鸡块君与FIFA22----ST表+DP 
官方题解：
 
 
 
  
#include 
using namespace std;
const int N = 200010;
int f[3][N][20];
char s[N];
signed main()
{
	int n,m;
    cin>>n>>m;
    cin>> s+1 ;
    for(int j=0;j<3;j++)
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='W')f[j][i][0]=1;
            else if(s[i]=='L')
            {
                if(!j)f[j][i][0]=0;
                else f[j][i][0]=-1;
            }
            else f[j][i][0]=0;
        }
    //类似于区间DP   初始化ST表
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<=0;j--)
        {
            if(l+(1<r)continue;
            x+=f[x%3][l][j];
            l+=(1< 
C.Baby’s first attempt on CPU----模拟 
 
#include 
#include 
#include 
using namespace std;
const int N = 110;
int n;
int g[N][4];
int add[N];
signed main()
{
	int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            cin>>g[i][j];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=3;j++)
            if(g[i][j])
            {
            	int now=0;
            	for(int k=i-j+1;k 
D.牛牛做数论—质数筛+欧拉函数+思维 
 

  
#include 
using namespace std;
int primes[10]={0,2,3,5,7,11,13,17,19,23};
bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)return false;
    return true;
}
signed main()
{
	int T;
    cin>>T;
    while(T--)
    {
        int n;cin>>n;
        if(n==1){cout<<-1< 
G.ACM is all you need—思维（这题很妙） 
 

  
#include 
#include 
#include 
using namespace std;
const int INF = 2e9+5,N=100010;
typedef pairPII;
int n,a[N];
PII check(int x,int y)
{
    if(x==y)return {0,-1};
    else if(x>y)return {(x+y+2)/2,INF};
    else return {-INF,(x+y-1)/2};
}
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        mapmp;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        for(int i=2;i<=n-1;i++)
        {
            auto [l1,r1]=check(a[i],a[i-1]);
            auto [l2,r2]=check(a[i],a[i+1]);
            l1=max(l1,l2);
            r1=min(r1,r2);
            if(l1>r1)continue;
            mp[l1]++,mp[r1+1]--;
        }
        if(mp[-INF]==0){printf("0n");continue;}
        int res=INF,k=0;
        for(auto [x,c]:mp)
        {
            if(x>=INF)break;
            k+=c;
            res=min(res,k);
        }
        printf("%dn",res);
    }
}
 
I.B站与各唱各的----组合数学+概率 
 

  
#include 
using namespace std;
#define int long long
const int mod=1e9+7;
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res%mod;
}
signed main()
{
	int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        cout<<(m*(qmi(2,n)-2)%mod*qmi(qmi(2,n),mod-2)%mod)< 
K.冒险公社----复杂DP 
 

  
#include 
#include 
#include 
using namespace std;
const int N = 100010;
int f[N][3][3][3];
char s[N];
int n;
//G 0
//R 1
//B 2
signed main()
{
    cin>>n;
    cin>> s+1;
    memset(f,-1,sizeof f);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
             for(int k=0;k<3;k++)
             {
                 int G=!i+!j+!k,R=(i==1)+(j==1)+(k==1);
                 if(G>R&&s[3]=='G')f[3][i][j][k]=G;
                 if(GR&&s[i]=='G')f[i][j][k][l]=max(f[i][j][k][l],f[i-1][k][l][p]+(j==0));
                        if(G					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713722.html
2022牛客寒假算法基础集训营1----ABCDGIK

发表评论

评论列表（0条）
