寒假测试1

大家好，我是讯享网，很高兴认识大家。

https://vjudge.net/problem/CodeForces-988A/origin

题意：给你n个数字，能不能在里面找到k个不同的数字，如果能就输出YES，再输出这些数字的下标（1<<i<<n）;不能就输出NO。(易)

思路：类似选择排序，两个for循环嵌套，里面的for循环判断输入的数字是否在前面出现过，出现就标记为0，没出现就记录不同数字的个数。

Input 5 3 15 13 15 15 12 Output YES 1 2 5 Input 5 4 15 13 15 15 12 Output NO Input 4 4 20 10 40 30 Output YES 1 2 3 4

讯享网

讯享网#include<iostream> using namespace std; int main() { 
    int a,b,c=0,i,j,k; cin>>a>>b; int m[a]; for(i=0; i<a; i++) cin>>m[i]; for(i=0; i<a; i++) { 
    for(j=i+1; j<a; j++) { 
    if(m[i]==m[j]) m[j]=0; } if(m[i]!=0) c++; } if(c<b) cout<<"NO"; else { 
    j=0; cout<<"YES"<<endl; for(i=0; i<a; i++) if(m[i]!=0) { 
    cout<<i+1<<" "; j++; if(j==b) break; } } return 0; }

https://vjudge.net/problem/CodeForces-988C/origin

题意：给你一个k，接下来有k个数组，找出两个数组，各自减去其中一个元素，剩下的元素之和相等，输出数组次序和所删元素位置。（偏难）

思路：分别记录去掉某个数的值，比较是否相等。

解题方法:1.这个题使用map<long long,pair<long long,long> >m，map的key记录的是每个去掉某个数的值，map的value记录的是所在的第几列和第几行。2.puts()函数输出字符串并换行。

Input 2 5 2 3 1 3 2 6 1 1 2 2 2 1 Output YES 2 6 1 2 Input 3 1 5 5 1 1 1 1 1 2 2 3 Output NO Input 4 6 2 2 2 2 2 2 5 2 2 2 2 2 3 2 2 2 5 2 2 2 2 2 Output YES 2 2 4 1

讯享网#include <iostream> #include <algorithm> #include <map> using namespace std; const int N=; int w[N]; map<int,pair<int,int>> mp; int main() { 
    int T; cin>>T; for(int k=1; k<=T; k++) { 
    int n; cin>>n; int sum=0; for(int i=1; i<=n; i++) { 
    cin>>w[i]; sum+=w[i]; } for(int i=1; i<=n; i++) { 
    int t=sum-w[i]; if(mp[t].first!=0) { 
    cout<<"YES"<<endl; printf("%d %d\n",mp[t].first,mp[t].second); printf("%d %d\n",k,i); return 0; } } for (int i=1; i<=n; i++) { 
    mp[sum-w[i]].first=k; mp[sum-w[i]].second=i; } } cout<<"NO"<<endl; return 0; }

https://vjudge.net/problem/CodeForces-988B/origin

题意：给你一堆字符串，把它们排成从上到下，上面一个是下面一个的子字符串的格式，若能就按格式全部输出，不能就输出“NO”.（注：子串指的是串中任意个连续的字符组成的子序列，而子序列可以是不连续的）（偏难）

补充：(1)输出连续子串假设字符串的长度为n，其非空子串的数目为n(n+1)/2个。

#include<iostream> #include<string> using namespace std; int main() { 
    string str; while(cin>>str) { 
    for(int i=0; i<str.size(); i++) { 
    for(int j=1; j<=str.size()-i; j++) { 
    cout<<str.substr(i,j)<<" "; } } } return 0; }

讯享网

思路：先排序，再判断子字符串。

解题方法：假设有两个字符串a、b, 现想判断a字符串是否包含b字符串，需要用到string库中的find函数与npos参数。
string::npos参数：npos是常数，用来表示不存在的位置，类型一般是std::container_type::size_type 许多容器都提供这个东西。取值由实现决定，一般是-1。
find函数：find函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于npos，但如果字符串不存在包含关系，那么返回值就一定是npos。

讯享网if (a.find(b) != string::npos) cout << "Yes!" << endl; else cout << "No!" << endl;

Input 5 a aba abacaba ba aba Output YES a ba aba aba abacaba Input 5 a abacaba ba aba abab Output NO Input 3 qwerty qwerty qwerty Output YES qwerty qwerty qwerty

讯享网#include<string> #include<algorithm> #include<iostream> using namespace std; string str[108]; int cmp(string a,string b) { 
    return a.size()<b.size(); } int main() { 
    int n; cin>>n; for(int i=0; i<n; i++) cin>>str[i]; sort(str,str+n,cmp); for(int i=0; i<n-1; i++) { 
    if(str[i+1].find(str[i])==str[i+1].npos) { 
    cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; for(int i=0; i<n; i++) { 
    cout<<str[i]<<endl; } return 0; }

https://vjudge.net/problem/CodeForces-988A/origin

思路：倒着循环相同就计为0，只保留最右边的数。

Input 6 1 5 5 1 6 1 Output 3 5 6 1 Input 5 2 4 2 4 4 Output 2 2 4 Input 5 6 6 6 6 6 Output 1 6

讯享网#include<iostream> using namespace std; int main() { 
    int a,i,j,c=0; cin>>a; int m[55]; for(i=0; i<a; i++) cin>>m[i]; for(i=a-1; i>=0; i--) { 
    for(j=i-1; j>=0; j--) { 
    if(m[i]==m[j]) m[j]=0; } if(m[i]!=0) c++; } cout<<c<<endl; for(i=0; i<a; i++) { 
    if(m[i]!=0) { 
    cout<<m[i]<<" "; } } return 0; }

https://vjudge.net/problem/CodeForces-978B/origin

题意：给你一串字母，这个字母里面不能有连续的三个x(子字符串)，不然就不符合条件。（易）

思路：连续的x超过两个就计数。

Input 6 xxxiii Output 1 Input 5 xxoxx Output 0 Input 10 xxxxxxxxxx Output 8

讯享网#include<iostream> #include<string> using namespace std; int main() { 
    int n; string a; cin>>n>>a; int i,s=0,sum=0; for(i=0; i<n; i++) { 
    if(a[i]=='x') { 
    s++; if(s>2)sum++; } else s=0; } cout<<sum<<endl; return 0; }

https://vjudge.net/problem/CodeForces-978C/origin

题意：给我们n个宿舍，每个宿舍ai(1<=i<=n)有一定的房间数，房间号bi按宿舍楼顺序排（如第一栋楼a1有3间房，a2有5间，则b5在第二栋楼第二间），给我们m封信，求每封信所对应房间号bi在哪栋宿舍哪一间，bi按顺序给出。（偏易）

Input 3 6 10 15 12 1 9 12 23 26 37 Output 1 1 1 9 2 2 2 13 3 1 3 12 Input 2 3 5  5 6  Output 1 5 2 1 2

讯享网#include<iostream> using namespace std; long long b,sum=0,a[]; int main() { 
    int n,t=1,m; cin>>n>>m; for(int i=1; i<=n; ++i) cin>>a[i]; for(int i=1; i<=m; ++i) { 
    cin>>b; while(sum+a[t]<b) sum+=a[t++]; cout<<t<<" "<<b-sum; cout<<endl; } }

相关推荐