头像

逆陽の葵




离线:1小时前


最近来访(60)
用户头像
Matsuko_2
用户头像
风-上
用户头像
无柒
用户头像
li2022
用户头像
violet_garden
用户头像
洛白さん
用户头像
xinyi127
用户头像
hhpiacm
用户头像
我肯定不记得
用户头像
yxc的小迷妹
用户头像
Snjjsvsand
用户头像
微雨双飞燕
用户头像
陌丨落
用户头像
StarLi9ht
用户头像
随.
用户头像
Eager
用户头像
吴世gay来喽
用户头像
夕闻
用户头像
fduytfkuhj
用户头像
Retro


逆陽の葵
11小时前

//自杀式枚举(有坑)

[NOIP2014 普及组] 珠心算测验

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

里面有一个坑,正常在枚举的过程中:5=1+4与5=2+3都是合法,看似合理。可是在这道题目中却是不
合法的,因为5被另外两个互不相等的数(即数对(1,4)与(2,3))枚举过两遍,导致输出结果大于正
确答案,所以要在枚举过程中实现去重(这道题好像没说清楚,故意挖坑hh)

最近老师出了一些测验题,请你帮忙求出答案。

(本题目为 2014NOIP 普及 T1)

输入格式

共两行,第一行包含一个整数 $n$,表示测试题中给出的正整数个数。

第二行有 $n$ 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。

输出格式

一个整数,表示测验题答案。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

2

提示

【样例说明】

由 $1+2=3,1+3=4$,故满足测试要求的答案为 $2$。

注意,加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 $100\%$ 的数据,$3 \leq n \leq 100$,测验题给出的正整数大小不超过 $10,000$。

代码

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int main()
{
    int n;
    int a[110];
    cin>>n;

    for(int i=0;i<n;++i)
    {
        scanf("%d",&a[i]);
    }

    sort(a,a+n);    //排序

    int res=0;
    vector<int> b={-1}; //用的是动态数组,最好是初始化第一个元素
    for(int i=0;i<n-2;++i)
    {
        for(int j=i+1;j<n-1;++j)
        {
            int t=a[i]+a[j];
            for(int k=j+1;k<n;++k)
            {
                if(t==a[k])
                {
                    bool repeat=false;
                    for(int u=0;u<b.size();++u) //这层循环用来去重
                    {
                        if(t==b[u])
                        {
                            repeat=true;
                            break;
                        }
                    }

                    if(repeat==false)
                    {
                        res++;
                    }
                    b.push_back(a[k]);
                    break;
                }
            }
        }
    }

    cout<<res;
    return 0;
}



[NOIP2008 普及组] ISBN 号码

题目描述

每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 $9$ 位数字、$1$ 位识别码和 $3$ 位分隔符,其规定格式如 x-xxx-xxxxx-x,其中符号 - 就是分隔符(键盘上的减号),最后一位是识别码,例如 0-670-82162-4就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言,例如 $0$ 代表英语;第一个分隔符 - 之后的三位数字代表出版社,例如 $670$ 代表维京出版社;第二个分隔符后的五位数字代表该书在该出版社的编号;最后一位为识别码。

识别码的计算方法如下:

首位数字乘以 $1$ 加上次位数字乘以 $2$ ……以此类推,用所得的结果 $ \bmod 11$,所得的余数即为识别码,如果余数为 $10$,则识别码为大写字母 $X$。例如 ISBN 号码 0-670-82162-4 中的识别码 $4$ 是这样得到的:对 067082162 这 $9$ 个数字,从左至右,分别乘以 $1,2,\dots,9$ 再求和,即 $0\times 1+6\times 2+……+2\times 9=158$,然后取 $158 \bmod 11$ 的结果 $4$ 作为识别码。

你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确,如果正确,则仅输出 Right;如果错误,则输出你认为是正确的 ISBN 号码。

输入格式

一个字符序列,表示一本书的 ISBN 号码(保证输入符合 ISBN 号码的格式要求)。

输出格式

一行,假如输入的 ISBN 号码的识别码正确,那么输出 Right,否则,按照规定的格式,输出正确的 ISBN 号码(包括分隔符 -)。

样例 #1

样例输入 #1

0-670-82162-4

样例输出 #1

Right

样例 #2

样例输入 #2

0-670-82162-0

样例输出 #2

0-670-82162-4

提示

2008 普及组第一题

主要是字符串的处理
整形数字转化成字符型数字:对应的整型数字加上48,再把字符型数字转化成整形数字:对应的字符型数字减去48(当然这只是局限于较低的精度)
会用substr函数就行

代码:

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
int main()
{
    string s;
    cin>>s;

    vector<int> a;

    for(int i=0;i<s.size();++i)
    {
        if(s[i]!='-')
        {
            int t=s[i]-48;  //临时变量t来存一下一个由字符型的数字转化而来的整型数字
            a.push_back(t);
        }
    }

    int sum=0;

    for(int i=0;i<a.size()-1;++i)
    {
        sum+=a[i]*(i+1);
    }

    int res=sum%11;
    char c;
    if(res==10)
    {
        c='X';
    }else
    {
        c=res+48;   //这里的临时变量c也是如此:先用字符型c来存一下由整型数字转化而来的字符型数字
    }

    if(c!=s[s.size()-1])
    {
        cout<<s.substr(0,s.size()-1)+c;
    }else
    {
        cout<<"Right";
    }
    return 0;
}



class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        if(nums.size()==0)  //当数组为空时
        {
            return -1;
        }else
        {
            sort(nums.begin(),nums.end());  //排序

            for(int i=0;i<nums.size();++i)
            {
                if(nums[i]<0||nums[i]>nums.size()-1)    //若其中有一个数是大于n-1或者小于0
                {
                    return -1;
                }
            }

            for(int i=0;i<nums.size();++i)  //只要前一项等于后一项就可判定为该数重复了
            {
                if(nums[i]==nums[i+1])
                {
                    return nums[i];
                }
            }
            return -1;
        }
    }
};



发现了sort一种用法,之前还没接触过hh
当sort函数给字符串排序时,会根据每个字符的ASCLL表值来排序
另外string 也有迭代器的功能,a.begin()和a.end()都能用,呃....之前没注意

[NOIP2008 提高组] 笨小猴

题目描述

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设 $\text{maxn}$ 是单词中出现次数最多的字母的出现次数,$\text{minn}$ 是单词中出现次数最少的字母的出现次数,如果 $\text{maxn}-\text{minn}$ 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

输入格式

一个单词,其中只可能出现小写字母,并且长度小于 $100$。

输出格式

共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出 Lucky Word,否则输出 No Answer

第二行是一个整数,如果输入单词是 Lucky Word,输出 $\text{maxn}-\text{minn}$ 的值,否则输出 $0$。

样例 #1

样例输入 #1

error

样例输出 #1

Lucky Word
2

样例 #2

样例输入 #2

olympic

样例输出 #2

No Answer
0

提示

【输入输出样例 1 解释】

单词 error 中出现最多的字母 $\texttt r$ 出现了 $3$ 次,出现次数最少的字母出现了 $1$ 次,$3-1=2$,$2$ 是质数。

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母 $\texttt i$ 出现了 $1$ 次,出现次数最少的字母出现了 $1$ 次,$1-1=0$,$0$ 不是质数。

(本处原题面错误已经修正)

noip2008 提高第一题

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;
int main()
{
    string s;
    cin>>s;

    sort(s.begin(),s.end());

    vector<int> a;

    for(int i=0;i<s.size();i++)
    {
        int cnt=0;
        int j=i;
        while(s[i]==s[j]&&j<s.size())
        {
            j++;
            cnt++;
        }
        a.push_back(cnt);
        i=j-1;  
    }

    sort(a.begin(),a.end());

    int t=a[a.size()-1]-a[0];
    if(t==2)
    {
        cout<<"Lucky Word"<<endl;
        cout<<t;
    }else if(t==0||t==1)
    {
        cout<<"No Answer"<<endl;
        cout<<'0';
    }else
    {
        bool is_prime=true;
        for(int i=2;i<=sqrt(t);++i)
        {
            if(t%i==0)
            {
                is_prime=false;
                break;
            }
        }
        if(!is_prime)
        {
            cout<<"No Answer"<<endl;
            cout<<'0';
        }else
        {
            cout<<"Lucky Word"<<endl;
            cout<<t;
        }
    }
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include<iostream>
using namespace std;

int main()
{
    int n,m;
    int a[100010];
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&a[i]);
    }

    while (m -- )
    {
        int x;
        scanf("%d",&x);

         //二分模板一
    `    int l=0;
        int r=n-1;

        while(l<r)
        {
            int mid=l+r>>1;
            if(a[mid]>=x)
            {
                r=mid;
            }else
            {
                l=mid+1;
            }
        `}

        if(a[l]!=x) //第一个while循环结束时l==r,此时已经左右边界相重合,若要查找的数字不在其中,那么该数不存在原数组中
        {
            printf("-1 -1\n");
        }else 
        {
    `        printf("%d ",l);

            //二分模板二
        `    int l=0;
            int r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(a[mid]<=x)
                {
                    l=mid;
                }else
                {
                    r=mid-1;
                }
            }
        `    printf("%d\n",l);
        }
    }

    return 0;
}



暴力模拟
题目的输入格有点麻烦,只能开数组来做了

密码密室

题目背景

大糕和盆友去玩密室逃脱,她们到了一个密码密室,她希望你能设计一个程序帮她逃出密室。

题目描述

密室中有一个密码锁,想要逃出密室,需要根据下面的提示还原密码锁。

密码锁是由 n 位数字旋钮组成,第 i 个旋钮上面写着数字 $a_i$。

密码锁上当前的每位数字都是经过一些旋转操作得到的,第 i 个旋钮是被旋转了 $b_i$次得到的。

其中旋转操作有两种:

向上移动(用 U 表示):它使第 i 个数字增加1。(如果对数字 $9$ 向上移动,它就会变成 $0$)。

向下移动(用 D 表示):它使第 i 个数字减少1。(如果对数字 $0$ 向下移动,它就会变成 $9$)。

大糕知道当前密码锁上的数字序列和每位数字旋钮被移动到当前状态的动作。

输入格式

第一行是一个整数 t($1≤t≤100$)–测试案例的数量。

测试案例:

第一行是一个整数 n($1≤n≤100$)–密码锁旋钮的数量。

第二行是 n 个整数 $a_i$($0≤a_i≤9$)–第 i 个旋钮上当前显示的数字。

接下来是 n行,其中第 i 行包含一个整数$b_i$($1≤b_i≤10$)和$b_i$个字符,(这些字符要么是 U ,要么是 D) – 分别表示第 i 个旋钮上旋转的次数,以及旋转的操作类型。

输出格式

对于每个测试,输出 n 个空格分隔的数字–密码锁的初始数字序列。

样例 #1

样例输入 #1

3
3
9 3 1
3 DDD
4 UDUU
2 DU
2
0 9
9 DDDDDDDDD
9 UUUUUUUUU
5
0 5 9 8 3
10 UUUUUUUUUU
3 UUD
8 UUDUUDDD
10 UUDUUDUDDU
4 UUUU

样例输出 #1

2 1 1 
9 0 
0 4 9 6 9

提示

在第一个测试案例中,我们可以证明初始序列是 $[2,1,1]$。在这种情况下,进行了以下移动操作。

在第一个旋钮上:
$$ 2\xlongequal[下移变成]{D}1\xlongequal[下移变成]{D}0\xlongequal[下移变成]{D}9 $$

第二个旋钮上:
$$ 1\xlongequal[上移变成]{U}2\xlongequal[下移变成]{D}1\xlongequal[上移变成]{U}2\xlongequal[上移变成]{U}3 $$
第三个旋钮上:
$$ 1\xlongequal[下移变成]{D}0\xlongequal[上移变成]{U}1 $$
最后的序列是$[9,3,1]$,与输入相符。

代码:

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    { 
        int m;
        cin>>m;
        int a[100];
        for(int i=0;i<m;++i)
        {
            cin>>a[i];
        }

        for(int i=0;i<m;++i)
        {
            int t;
            cin>>t;
            char ch[100];

            for(int k=0;k<t;++k)
            {
                cin>>ch[k];
            }

            for(int j=0;j<t;++j)
            {
                if(ch[j]=='U')
                {
                    if(a[i]==0)
                    {
                        a[i]=9;
                    }else
                    {
                        a[i]--;
                    }
                }else if(ch[j]=='D')
                {
                    if(a[i]==9)
                    {
                        a[i]=0;
                    }else
                    {
                        a[i]++;
                    }
                }
            }
        }

        for(int i=0;i<m;++i)
        {
            cout<<a[i]<<' ';
        }

        cout<<endl;
    }
    return 0;
}



#include<iostream>
using namespace std;

long long fun(long long  a,long long b)
{
    if(b<0)
    {
        return -abs(a);
    }else
    {
        return abs(a);
    }
}
int main()
{
    long long a,b;
    cin>>a>>b;

    cout<<fun(a,b);
    return 0;
}



糖果算法大赛

题目背景

小糕作为糖果算法大赛的糖果采购员,她需要根据比赛结果中所有团队得到的糖果总数进行采购,但是她的算数能力不好,所以希望你来设计一个算法来帮她得出她需要购买的糖果总数。

题目描述

在糖果算法大赛中,糖果的分配方式如下:
每当一个团队闯过一关,该团队就会得到一颗糖果。
当这个关卡第一次被某个团队闯过之后,那个这个团队将会得到一颗额外的糖果

大赛有26个关卡,标记为$A,B,C,…,Z$。

小糕会得到一个字符串 s 表示大赛中所有团队闯过关卡的顺序。
i 个字符 $s_i$ 表示第 $s_i$关已经被某个队伍成功闯过。(没有那个队伍会重复闯过同一关。)

你的目标是统计出所有队伍在大赛中所得的糖果总数。(由于一些关卡很难,所以可能没有被任何一个队伍闯过。)

输入格式

第一行是一个整数 t($1≤t≤100$)–测试用例的数量。

每个测试用例:

第一行是一个整数 n($1≤n≤50$)–字符串的长度。

第二行是一个长度为 n 的字符串 s,由大写英文字母组成,表示已闯过关卡的顺序。

输出格式

对于每个测试,输出一个整数–所有队伍得到糖果的总数。

样例 #1

样例输入 #1

6
3
ABA
1
A
3
ORZ
5
BAAAA
4
BKPT
10
CODEFORCES

样例输出 #1

5
2
6
7
8
17

提示

在第一个测试用例中,需要采购 5 颗糖果。

关卡A被解决了。该队得到2颗糖果:一颗是因为他们闯过了关卡A,另一颗是因为他们是第一个闯过关卡A的队伍。

关卡B被解决了。该队得到2颗糖果:一颗是因为他们闯过了关卡B,另一颗是因为他们是第一个闯过关卡B的队伍。

关卡A被解决了。该队只得到1颗糖果,因为他们闯过了这个关卡。(他们没有得到额外的糖果,因为他们不是第一个闯过关卡 A 的团队)。

所以所有队伍得到的糖果总数是$2+2+1=5$。

在第二个测试用例中,只有关卡 A 被闯过。

闯过这个关卡的队伍得到了2颗糖果:一颗是因为他们闯过了关卡A,另一颗是因为他们是第一个闯过关卡 A 的队伍。

思路:暴力枚举+无脑模拟

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

int main()
{
    int n,m;
    cin>>n;

    while(n--)
    {
        cin>>m;
        char s[60];

        for(int i=0;i<m;++i)
        {
            cin>>s[i];
        }

        int cnt=0;
        for(int i=0;i<m;++i)
        {
            int flag=1;
            for(int j=i-1;j>=0;j--)
            {
                if(s[j]==s[i])
                {
                    flag=0;
                }
            }

            if(flag==0)
            {
                cnt++;
            }else if(flag==1)
            {
                cnt+=2;
            }
        }

        cout<<cnt<<endl;
    }
    return 0;
}



#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int main()
{
    string s,s1,s2;
    char ch;

    while (cin >> ch, ch != ',') s += ch;
    while (cin >> ch, ch != ',') s1 += ch;
    while (cin >> ch) s2 += ch;

    int n=s.find(s1);
    int m=s.rfind(s2);

    if(n!=-1&&m!=-1&&(n+s1.size()-1)<m)
    {
        cout<<m-n-s1.size();
    }else
    {
        cout<<"-1";
    }

    return 0;
}



#include <iostream>
using namespace std;

int n;
string str[200];  //字符串数组,好家伙!`每个数组里面储存一个字符串`。呃,不过也正常,之前我一直用的是vector来储存字符串

int main()
{
    while (cin>>n,n!=0) //这个输入方式能够让你赢在起跑线上,非常`《高效》`的读入数据的方式
    {
        int len = 200; //先假定最大的公共后缀长度 `len` 为200,为什么要定为200呢?后面再给你解释 hh

        for (int i=0; i<n; i++ )    //这个for循环来处理每次输入的n个字符串
        {
            cin >> str[i];  //将这n个字符串一同读入预先准备好的字符串数组中。在哪里准备好的呢?当然在被我称为“好家伙”的全局变量str[200]。

            if (len > str[i].size())    //这里搞个if语句,想必大家应该明白为什么前面的len要定为200了吧,呃,还不明白啊
            {
                len = str[i].size();    //其实呢,这里是为了找出这n个字符串中长度最小的字符串,并把其字符串长度赋给len,这样是为了考虑那个最小的字符串就是最大的公共后缀
            }
        }

        while (len!=0)  //正式开始枚举,循环结束条件是最大的公共后缀长度不为0,一旦为0,说明每次输入的n个字符串们没有公共后缀
        {
            bool success = true;    //标记1 success ,true表示已经找到最长的公共后缀

            for (int i = 1; i < n; i++ )    //这是个外循环,为什么初始值是i = 1呢?因为我要拿比
            {
                bool is_same = true;    //标记2 is_same 表示下标为0的字符串与后面下标为1,2,....n的字符串最后一个字符到以len值截止的后字符串这一段区间中的字符是相同的

                for (int j = 1; j <= len; j ++ )
                {
                    if (str[0][str[0].size() - j] != str[i][str[i].size() - j]) //千万不要被它的形式str[][]所迷惑,这家伙不是二维数组哦,是什么呢?这个表示的是一个字符数组中的一个字符串中的一个字符(禁止套娃)
                    {
                        is_same = false;    
                        break;
                    }
                }

                if (is_same == false)   //如果字符不同,那么直接意味着没有找到公共后缀
                {
                    success = false;
                    break;
                }
            }

            if (success == true)    //如果在以当前len值的范围内,字符全部相同,那么意味着找到了公共后缀
            {
                break;
            }

            len -- ;    //这是承接上面没有找到公共后缀的情况(success == false) ,那么我们就缩小len 值,继续寻找
        }

        cout << str[0].substr(str[0].size() - len) << endl;     //调用substr函数,输出公共后缀
    }

    return 0;
}