慕容琳的后花园
慕容琳的后花园
hgoi#20190428

T1-Diversity

给你一个小写字母串和一个数k,要求最少改几个数能使字符串中有k个不同的小写字母
如果无法达到,输出impossible

解法

就是统计小写字母串里有几个不同的小写字母
至于无解的情况是k>len

ac代码

#include<bits/stdc++.h>
using namespace std;
char s[1010];
int len,k,ans,a[50];
int main()
{
    cin >> s >> k,len=strlen(s);
    if(k>len){puts("impossible");return 0;}
    for(int i=0;i<len;i++)if(!a[s[i]-'a'+1])a[s[i]-'a'+1]=1,ans++;
    cout << max(0,k-ans) << endl;
    return 0;
}

T2-Rectangles

给一个01矩阵,求有多少子点集满足:
1、点全是0或点全是1
2、点都在同一行或同一列上

解法

也很简单啊=-=,统计出每行每列0和1的数量,然后就是手推一下公式
发现是组合数求和,直接(1<<x)即可
tips:不开long long见祖宗

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,a[100],b[100];
long long ans;
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> x;
            if(x)a[i]++,b[j]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=(1ll<<a[i])+(1ll<<(m-a[i]))-2;
    }
    for(int i=1;i<=m;i++)
    {
        ans+=(1ll<<b[i])+(1ll<<(n-b[i]))-2;
    }
    cout << ans-n*m << endl;
    return 0;
}

T3-Removing Columns

给定一个字符矩阵
要求最少删几列能使这个矩阵每一行的字符串都是按照字典序从小到大排列的

解法

直接模拟嘛,优先删除前面的,对于后面的,只有前面相等时才需要判断是否符合

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,flg,fg,last=1,d[110];
char s[110][110];
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin >> s[i][j];
    for(int i=1;i<=m;i++)
    //枚举每一列
    {
        flg=0;
        for(int j=1;j<n;j++)
        //枚举每一行,判断是否符合标准 
        {
            fg=0;
            for(int k=1;k<i;k++)
                if(s[j][k]<s[j+1][k]&&!d[k]){fg=1;break;}
            if(fg)continue;
            if(s[j][i]>s[j+1][i]){flg=1;break;}
        }
        if(flg==1)d[i]=1,ans++;
    }
    cout << ans << endl;
    return 0;
}

T4-Woodcutters

给定每棵树在数轴上的坐标和树的高度,每棵树砍倒后会占据(x-h,x)或(x,x+h)
没砍倒的树占据点x,一个点只能被占据一次,问最多能砍几棵树

解法

显然的贪心,对于每一棵树,优先向左倒,之后才向右倒
至于证明,如果这棵树向右倒使后面那棵树不能向左倒,答案是没有损失的,对后面的区间也没有影响

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,x[100010],h[100010],opt[100010],ans;
int main()
{
    scanf("%d",&n),x[0]=-0x3f3f3f3f,x[n+1]=0x7fffffff;
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&h[i]);
    for(int i=1;i<=n;i++)
    {
        if(x[i]-h[i]>x[i-1]+opt[i-1]*h[i-1])ans++;
        else if(x[i]+h[i]<x[i+1])opt[i]=1,ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T5-Bear and Prime 100

竟然是道交互题!然而很简单
我们可以输出2~100的20个数,题目会告诉我们它是否能整除x
最后让我们判断x是质数还是合数

解法

看起来有点难,但是想一想质数怎么判断
先把2-50的质数求出来,我们可以询问2-50的质数,再询问2-10的质数的平方
这样有什么用呢,如果它是质数,一定只会被其中0或1个数整除,而如果不是质数,一定能分解成2个及以上质数的积
而如果2个质数是相同的,只可能是2-10的质数的平方,这样刚好询问19次

ac代码

#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
int main()
{
    puts("2");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("4");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("3");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("9");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("5");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("25");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("7");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("49");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("11");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("13");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("17");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("19");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("23");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("29");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("31");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("37");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("41");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("43");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    puts("47");
    fflush(stdout);
    cin >> s;
    if(s[0]=='y')ans++;
    if(ans>=2)puts("composite");
    else puts("prime");
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20190428
T1-Diversity 给你一个小写字母串和一个数k,要求最少改几个数能使字符串中有k个不同的小写字母 如果无法达到,输出impossible 解法 就是统计小写字母串里有几个不同的小写字母 至于无…
扫描二维码继续阅读
2019-05-06
功能