2019 计蒜之道 复赛

Wesley13
• 阅读 543

A题:外教 Michale 变身大熊猫

题目链接:https://nanti.jisuanke.com/t/39611

题解:

2019 计蒜之道 复赛

2019 计蒜之道 复赛 2019 计蒜之道 复赛

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int  maxx = 5e5+10;
const int mod = 998244353;
struct node{LL len,num;}tree[maxx];
int a[maxx],s[maxx];
LL len1[maxx],len2[maxx],num1[maxx],num2[maxx];
LL dp[maxx];
int n;
LL inv(LL x)
{
    LL b=mod-2,ans=1;
    while(b)
    {
        if(b&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        b>>=1;
    }
    return ans;
}
void up(int x,node t)
{
    for(int i=x;i<=n;i+=(i&(-i)))
    {
        if(tree[i].len<t.len)tree[i]=t;
        else if(tree[i].len==t.len)tree[i].num+=t.num,tree[i].num%=mod;
        //注意这里也要取一下模
    }
}
node getmax(int x)
{
    node res;
    res.len=0;res.num=1;
    for(int i=x;i>0;i-=(i&(-i)))
    {
        if(res.len<tree[i].len)res=tree[i];
        else if(res.len==tree[i].len)res.num+=tree[i].num,res.num%=mod;
        //注意这里也要取一下模
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=a[i];
        tree[i].len=tree[i].num=0;
    }
    sort(s+1,s+1+n);
    int t=unique(s+1,s+1+n)-s;
    node ans;
    ans.len=ans.num=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(s+1,s+t,a[i])-s;//离散化
        node temp=getmax(a[i]-1);
        temp.len++;
        up(a[i],temp);
        len1[i]=temp.len;num1[i]=temp.num;
        //cout<<len1[i]<<' '<<num1[i]<<endl;
        if(ans.len<temp.len)ans=temp;
        else if(ans.len==temp.len)ans.num+=temp.num,ans.num%=mod;
        sum=max(sum,a[i]);
    }
    for(int i=1;i<=n;i++)
        tree[i].len=tree[i].num=0;
    for(int i=n;i>=1;i--)
    {
        a[i]=a[i]*(-1)+sum+1;
        //cout<<a[i]<<endl;
        node temp=getmax(a[i]-1);
        temp.len++;
        up(a[i],temp);
        len2[i]=temp.len;num2[i]=temp.num;
        //cout<<len2[i]<<' '<<num2[i]<<endl;
    }
    LL q=inv(ans.num);
    for(int i=1;i<=n;i++)
    {
        if(len1[i]+len2[i]==ans.len+1)printf("%lld ",num1[i]*num2[i]%mod*q%mod);
        else printf("0 ");
    }
    return 0;
}

View Code

B题:个性化评测系统

题目链接:https://nanti.jisuanke.com/t/39612

直接暴力,枚举每一张牌判断可不可以胡,判断的时候要先枚举对子并删去再判断可不可行,有一种可行就说明这张牌可以胡

2019 计蒜之道 复赛 2019 计蒜之道 复赛

#include<bits/stdc++.h>
using namespace std;
int ff(int *a)
{
    for(int i=1;i<=7;i++)
        if(a[i]==1||a[i]==2)return 0;
    return 1;
}
int f(int *a)
{
    int s[20];
    for(int i=1;i<=9;i++)
        s[i]=a[i];
    for(int j=1;j<=7;j++)
    {
        if(s[j]>=3)s[j]-=3;
        if(s[j]==1)
        {
            if(s[j+1]&&s[j+2])
            {
                s[j+1]--;s[j+2]--;
            }
            else return 0;
        }
        if(s[j]==2)
        {
            if(s[j+1]>=2&&s[j+2]>=2)
            {
                s[j+1]-=2;s[j+2]-=2;
            }
            else return 0;
        }
    }
    if(s[8]==1||s[8]==2||s[9]==1||s[9]==2)return 0;
    return 1;
}
int see(int *a,int *b,int *c,int *d)
{
    int s[20],p[20],m[20],z[20];
    int flag;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
        }
        if(s[i]>=2)s[i]-=2;//枚举并删去对子
        if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
        }
        if(p[i]>=2)p[i]-=2;
        if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
        }
        if(m[i]>=2)m[i]-=2;
        if(f(s)&&f(p)&&f(m)&ff(z))return 1;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
        }
        if(z[i]>=2)z[i]-=2;
        if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
    }
    return 0;
}
int main()
{
    char ch[5];
    while(cin>>ch)
    {
        int s[20]={0},p[20]={0},m[20]={0},z[20]={0};
        if(ch[1]=='s')s[ch[0]-'0']++;
        if(ch[1]=='p')p[ch[0]-'0']++;
        if(ch[1]=='m')m[ch[0]-'0']++;
        if(ch[1]=='z')z[ch[0]-'0']++;
        for(int i=2;i<=13;i++)
        {
            cin>>ch;
            if(ch[1]=='s')s[ch[0]-'0']++;
            if(ch[1]=='p')p[ch[0]-'0']++;
            if(ch[1]=='m')m[ch[0]-'0']++;
            if(ch[1]=='z')z[ch[0]-'0']++;
        }
        for(int i=1;i<=9;i++)
        {
            if(m[i]>=4)continue;
            m[i]++;
            if(see(s,p,m,z))printf("%dm\n",i);
            m[i]--;
        }
        for(int i=1;i<=9;i++)
        {
            if(s[i]>=4)continue;
            s[i]++;
            if(see(s,p,m,z))printf("%ds\n",i);
            s[i]--;
        }
        for(int i=1;i<=9;i++)
        {
            if(p[i]>=4)continue;
            p[i]++;
            if(see(s,p,m,z))printf("%dp\n",i);
            p[i]--;
        }
        for(int i=1;i<=7;i++)
        {
            if(z[i]>=4)continue;
            z[i]++;
            if(see(s,p,m,z))printf("%dz\n",i);
            z[i]--;
        }
    }
    return 0;
}
/*3m 3m 3m 4m 5m 6m 6m 6m 1z 1z 1z 2z 2z
1p 1p 1p 4p 5p 6p 9p 9p 9p 8p 8p 8p 8p
1s 1s 1s 1s 2s 2s 2s 2s 3p 3p 3p 5p 5p
1s 1s 2s 3s 5s 5s 6s 6s 7s 7s 7s 8s 9s
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s*/

View Code

D题:“星云系统”

题目链接:https://nanti.jisuanke.com/t/39614

第一种解法:用单调栈

2019 计蒜之道 复赛 2019 计蒜之道 复赛

#include<bits/stdc++.h>
using namespace std;
stack<char>q;
char a[5000010],b[5000010];
int main()
{
    scanf("%s",a);
    int s=strlen(a);
    int k;
    scanf("%d",&k);
    q.push(a[0]);
    for(int i=1;i<s;i++)
    {
        while(!q.empty())
        {
            char t=q.top();
            if(t<=a[i])
            {
                //q.push(a[i]);
                break;
            }
            else
            {
                if(s-i+q.size()>k)q.pop();
                else break;
            }
        }
        q.push(a[i]);
    }
    int t=0;
    while(!q.empty())
    {
        b[++t]=q.top();q.pop();
    }
    for(int i=t;i>t-k;i--)
        printf("%c",b[i]);
    return 0;
}

View Code

第二种解法:用26个vector存字母位置然后暴力,好像叫序列自动机

2019 计蒜之道 复赛 2019 计蒜之道 复赛

#include<bits/stdc++.h>
using namespace std;
const int maxx = 5e6+10;
vector<int>q[30];
char a[maxx];
int pos[30],len;
int find(int i,int s)//pos[i]用来标记用过的位置
{
    while(q[i][pos[i]]<s && pos[i]<q[i].size())
        pos[i]++;
    return q[i][pos[i]];
}
void dfs(int s,int k)//s为当前位置
{
    if(!k)return;
    for(int i=0;i<26;i++)
    {
        int t=find(i,s);
        if(t>=s&&len-t+1>=k)
        {
            printf("%c",i+'a');
            dfs(t+1,k-1);
            return;
        }
    }
}
int main()
{
    for(int i=0;i<26;i++)q[i].push_back(0);
    scanf("%s",a+1);
    len=strlen(a+1);
    for(int i=1;i<=len;i++)
        q[a[i]-'a'].push_back(i);
    int k;
    scanf("%d",&k);
    dfs(1,k);
    return 0;
}

View Code

E题:撑起信息安全“保护伞

题目链接:https://nanti.jisuanke.com/t/39615

题解:

2019 计蒜之道 复赛

就是找 ")(" 和 合法的"()"

2019 计蒜之道 复赛 2019 计蒜之道 复赛

#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e6+10;
char a[maxx],b[maxx];
stack<char>q;
int main()
{
    scanf("%s",a);
    int s=strlen(a);
    strcpy(b,a);
    int flag=0;
    for(int i=s-1;i>=1;i--)
    {
        if(b[i]=='('&&b[i-1]==')')//找")("
        {
            b[i]=')';b[i-1]='(';
            int t=0;
            for(int j=i+1;j<s;j++)
            {
                if(b[j]=='(')q.push(b[j]);
                else
                {
                    if(b[j]==')'&&!q.empty())q.pop();
                    else if(b[j]==')'&&q.empty())t++;
                }
            }
            for(int j=i+1;j<i+1+t;j++)
                b[j]=')';
            for(int j=i+1+t;j<s-1;j+=2)
                b[j]='(',b[j+1]=')';
            flag=1;break;
        }
    }
    if(flag)printf("%s\n",b);
    else
    {
        for(int i=0;i<s-2;i+=2)
            printf("()");
        printf("\n");
    }
    strcpy(b,a);
    flag=0;
    for(int i=s-1;i>=1;i--)
    {
        if(b[i]==')'&&b[i-1]=='(')//找交换后合法的"()"
        {
            while(!q.empty())q.pop();
            b[i]='(';b[i-1]=')';
            int j;
            for(j=0;j<s;j++)
            {
                if(b[j]=='(')q.push(b[j]);
                else
                {
                    if(b[j]==')'&&!q.empty())q.pop();
                    else break;
                }
            }
            if(j<s||!q.empty())b[i]=')',b[i-1]='(';
            else
            {
                int t=0;
                for(int k=i+1;k<s;k++)
                    if(b[k]=='(')t++;
                for(int k=i+1;k<i+1+t;k++)b[k]='(';
                for(int k=i+1+t;k<s;k++)b[k]=')';
                flag=1;break;
            }
        }
    }
    if(flag==1)printf("%s",b);
    else
    {
        s=s+2;
        for(int i=1;i<=s/2;i++)
            printf("(");
        for(int i=s/2+1;i<=s;i++)
            printf(")");
    }
    return 0;
}
/*((((()))))()()()()(())
((()())())*/

View Code

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Android蓝牙连接汽车OBD设备
//设备连接public class BluetoothConnect implements Runnable {    private static final UUID CONNECT_UUID  UUID.fromString("0000110100001000800000805F9B34FB");
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这