A - 前m大的数
这题我直接暴力解题，数字两两结合，排序输出，废话不多说了，先上代码
#include<iostream>
#include<algorithm>
using namespace std;
int sum[4500000],a[10086]; **//N(N<=3000)，N*(N-1)/2，可以得到两项和的数组，粗略算一下这个数够用了**
int main()
{
int n,m,k;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
cin>>a[i];
k=0; **//注意，每输入一次，计算N*(N-1)/2要清零**
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
sum[k]=a[i]+a[j]; ** //暴力求和**
k++;
}
}
sort(sum,sum+k); ** //排序sort比较快**
for(int i=k-1;i>k-m;i--)
cout<<sum[i]<<" ";
cout<<sum[k-m]<<endl; ** //我特意瞅了一眼输出，果然有坑，最后没空格**
}B - 稳定排序
如果对于数组中出现的任意a[i],aj,其中a[i]==a[j]，在进行排序以后a[i]一定出现在a[j]之前，则认为该排序是稳定的，注意排序方式。
对于每组数据，如果算法是正确并且稳定的，就在一行里面输出"Right"。如果算法是正确的但不是稳定的，就在一行里面输出"Not Stable"，并且在下面输出正确稳定排序的列表，格式同输入。如果该算法是错误的，就在一行里面输出"Error",并且在下面输出正确稳定排序的列表，格式同输入。
结构体储存数据，排序，对比，判断输出。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct s{
int score;
int que;
char name[55];
}a[360],b[360];
int cmp(s x,s y)
{
return x.score!=y.score?x.score>y.score:x.que<y.que; //排序方式，稳定排序处理
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a)); //清空数据
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)
{
scanf("%s%d",&a[i].name,&a[i].score);
a[i].que=i; //位置序号记录
}
sort(a,a+n,cmp);
int f1=1,f2=1;
for(int i=0;i<n;i++)
{
scanf("%s%d",&b[i].name,&b[i].score);
if(strcmp(a[i].name,b[i].name)!=0) f1=0; //姓名比较
if(a[i].score!=b[i].score) f2=0; //分数比较
}
if(f1+f2==2) printf("Right\n"); //判断阶段
else if(f1==0&&f2==1)
{
printf("Not Stable\n");
for(int i=0;i<n;i++)
{
printf("%s %d\n",a[i].name,a[i].score);
}
}
else
{
printf("Error\n");
for(int i=0;i<n;i++)
{
printf("%s %d\n",a[i].name,a[i].score);
}
}
}
return 0;
}C-开门人和关门人
比较时间来输出开关门人的证件号码，用结构体可以实现，由于时间输入的格式，我觉得一般直接比较数字的方法行不通，利用char[]和strcmp()函数进行比较，比较合适。
#include<bits/stdc++.h>
using namespace std;
struct
{
char num[1000];
char tim1[1000];
char tim2[1000];
}st[1000]; //结构体设定好，证件号，出入时间
int main()
{
int t,n,max,min;
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>st[i].num;
cin>>st[i].tim1;
cin>>st[i].tim2;
}
min=0,max=0;
for(int i=0;i<n;i++)
{
if(strcmp(st[min].tim1,st[i].tim1)>0) //注意strcmp（）实现比较时间。
min=i;
if(strcmp(st[max].tim2,st[i].tim2)<0)
max=i;
}
cout<<st[min].num<<" "<<st[max].num<<endl;
}
return 0;
}D - EXCEL排序
先读一遍题，发现题目中输入数据和题干，我觉得结构体妥妥的，然后比较一下并排序，开始注意排序
当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
接下来码代码就行了，肝
#include<bits/stdc++.h.>
using namespace std;
struct s{
char num[10];
char name[10];
int sorce;
}t[100010];
bool cmp1(s a,s b){ //学号递增排序
return strcmp(a.num,b.num)<0;
}
bool cmp2(s a,s b){ //按照姓名的非递减字典序排序
if(strcmp(a.name,b.name)) return strcmp(a.name,b.name)<0;
else return strcmp(a.num,b.num)<0;
}
bool cmp3(s a,s b){ //按成绩的非递减排序
if(a.sorce!=b.sorce) return a.sorce<b.sorce;
else return strcmp(a.num,b.num)<0;
}
int main(){
int m,n,count=0;
while(scanf("%d%d",&m,&n)!=EOF){
if(m==0) break;
int i;
for(i=0;i<m;i++){
scanf("%s %s %d",&t[i].num,&t[i].name,&t[i].sorce);
}
switch(n){ //选择数，试试switch比if看起来整洁点
case 1:sort(t,t+m,cmp1);break;
case 2:sort(t,t+m,cmp2);break;
case 3:sort(t,t+m,cmp3);break;
}
printf("Case %d:\n",++count); //注意输出格式
for(i=0;i<m;i++){
printf("%s %s %d\n",t[i].num,t[i].name,t[i].sorce);
}
}
return 0;
}
E-{A}+{B}
考察set函数，把两个集合元素插入一个集合，去重，输出，上代码
#include<iostream>
#include<set>
using namespace std;
set<int>se;
int main()
{
int n,m;
while(cin>>n>>m)
{
n=n+m; //两个集合的元素书混一起，方便插入到同一个集合进行去重
se.clear(); //注意清空上一次集合内部残存元素
while(n--)
{
int a;
cin>>a;
se.insert(a);
}
int flag=0; //下文空格输出有限制，最后一个元素输出不要空格
set<int>::iterator it;
for(it=se.begin();it!=se.end();it++)
{
if(flag!=0) //回收flag
cout<<" ";
cout<<*it;
flag++;
}
cout<<endl;
}
return 0;
}F - 水果
多组数据组合，考虑到结构体，水果数，考虑到map去计数，组合一下就出来了
上代码
#include<iostream>
#include<map>
#include<string>
using namespace std;
struct my{
map<string,int>myma; //结构体套map，组合地名。水果名，数字便于输出
};
int main()
{
map<string,my>ma;
map<string,my>::iterator it; //迭代器
map<string,int>::iterator mymait;
string fruit,place;
int num;
int n,t;
cin>>t;
while(t--)
{
ma.clear();
cin>>n;
while(n--)
{
cin>>fruit>>place>>num;
ma[place].myma[fruit]+=num;
}
for(it=ma.begin();it!=ma.end();it++)
{
cout<<it->first<<endl;
for(mymait=it->second.myma.begin();mymait!=it->second.myma.end();mymait++) //这个结构体套map有点绕，总之mymait->first是水果名，mymait->second是水果数
{
cout<<" |----"<<mymait->first<<"("<<mymait->second<<")"<<"\n";
}
}
if(t!=0)cout<<"\n"; //注意大坑，最后\n要看好结构
}
return 0;
}G - 不重复数字
用map函数对每次输入进行检测，如果重复了就不输出，不重复就输出，上代码
#include<bits/stdc++.h>
using namespace std;
map<int,int>ma;
int main()
{
long long int t;
scanf("%lld",&t); //scanf,printf,快一点
while(t--)
{
long long int n,a,flag=0;
scanf("%lld",&n);
ma.clear();
for(long long int i=0;i<n;i++)
{
scanf("%lld",&a);
if(ma[a]==0) //检测是否重复出现过
{
if(flag!=0) //注意输出格式，最后一个不输出空格，此处回收flag
printf(" ");
printf("%lld",a);
}
flag++;
ma[a]++; //数出数字出现次数
}
printf("\n");
}
return 0;
}H - 表达式括号匹配
检测（和）两个字符是否出现次数相同，签到题，直接上代码
#include<bits/stdc++.h>
using namespace std;
map<int,int>ma;
int main()
{
char s[3000];
int n=0,m=0;
cin>>s;
for(int i=0;i<strlen(s);i++)
{
if(s[i]=='(')
n++;
if(s[i]==')')
m++;
}
if(n==m)
cout<<"YES";
else
cout<<"NO";
}I - 合并果子
priority_queue和queue不同的就在于我们可以自定义其中数据的优先级，让优先级高的排在队列前面，优先出队，每次把最小代价的排出来，然后合并，用priority_queue岂不美哉，每一次消耗最小从而得出最优解，废话不多说上代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> que;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,a;
cin>>n;
while(que.size()) que.pop(); //清空上一次的参与元素
while(n--)
{
cin>>a;
que.push(a); //把元素加到priority_queue
}
long long int sum=0; //和的话就大些比较好，long long 稳点
while(que.size()>=2) //保证最后是两堆果子
{
int x=que.top();que.pop(); //排出最小
int y=que.top();que.pop(); //第二小
sum+=x+y; //总消耗
que.push(x+y); //合并后的果子堆别忘了也要计入
}
cout<<sum<<endl;
}
return 0;
} J - Covered Points Count
建立一个数组，每读一条线段进来，就把线段上的点都加1，最后遍历数组计算出值，
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
map<ll,int>ma;
map<ll,int>::iterator it;
ll cnt[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
ll l,r;
cin>>l>>r;
ma[l]++; //原则，头部加，末尾后退一步减
ma[r+1]--;
}
ll last=0; //当前区间起点
int ans=0;
for(it=ma.begin();it!=ma.end();it++) //遍历了
{
if(it==ma.begin())
{
last=it->first;
ans+=it->second; //此点覆盖
continue;
}
cnt[ans]+=it->first-last;
last=it->first;
ans+=it->second;
}
for(int i=1;i<=n;i++)
{
cout<<cnt[i];
if(i==n)
cout<<"\n";
else
cout<<" ";
}
return 0;
} K - Ignatius and the Princess IV
计算出现次数，map是个很好的选择，当然不用STL也可以，不过还是熟练一下STL更好，上代码
#include<iostream>
#include<map>
using namespace std;
map<int,int>ma;
int main()
{
int n;
while(cin>>n)
{
ma.clear(); //记得清空参与元素
for(int i=0;i<n;i++)
{
int a;
cin>>a;
ma[a]++; //计算出现次数
}
int flag=0; //因为要控制输出输出次数
map<int,int>::iterator it;
for(it=ma.begin();it!=ma.end();it++)
{
int t=it->second;
if(t>=(n+1)/2&&flag==0)
{
int q=it->first;
cout<<q<<endl;
flag--;
}
}
}
return 0;
} L - Stones
重载运算符
<返回类型说明符> operator <运算符符号>(<参数表>) { <函数体> }
优先队列应用，上代码吧
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>mp;
struct cmp
{
bool operator()(mp a,mp b) //first表位置，second表距离
{
if(a.first==b.first) //距离从小到大排序
return a.second>b.second;
return a.first>b.first;
}
}
priority_queue<mp,vector<mp>,cmp>que;
int main()
{ //优先队列插入
int t,n,a,b;
cin>>t;
while(t--)
{
cin>>n;
while(!que.empty())que.pop(); //清空残余元素
for(int i=0;i<n;i++)
{
cin>>a>>b;
que.push(mp(a,b))
}
int num=1;
mp next;
while(!que.empty())
{
next=que.top();
que.pop();
if(num&1)que.push(mp(next.first+next.second,next.second));
num++;
}
printf("%d\n",next.first);
}
return 0;
}M - SnowWolf's Wine Shop
multiset是<set>库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。利用这个特性，存酒。</set>
#include<stdio.h>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int t,a,b,c,x,cas=1;
scanf("%d",&t);
while(t--)
{
multiset<int > wine;
wine.clear(); //记得清空残余量
scanf("%d%d%d",&a,&b,&c);
printf("Case %d:\n",cas++);
while(a--)
{
scanf("%d",&x);
wine.insert(x); //输入
}
while(b--)
{
scanf("%d",&x);
multiset<int >::iterator t=wine.lower_bound(x);
if(t==wine.end()||*t-x>c)printf("-1\n");
else
{
printf("%d\n",*t);
wine.erase(t); //记得清除
}
}
}
return 0;
}N - Alice, Bob and Candies
两个小朋友从两边吃糖，吃的一方要比上一次一方吃的多，求次数与双方吃糖数，模拟两方吃糖就行了
上代码吧。
#include <iostream>
using namespace std;
int const N=1e5+5;
int c[N]; //存糖
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>c[i];
n--;
int x=0,y=0,last=0,num=0; //last存上次吃糖数，num是次数，x和y是两个小朋友吃糖数
for(int i=0;i<=n;)
{
num++;
int sum=c[i++];
while(sum<=last&&i<=n) sum+=c[i++]; //模拟吃糖
x+=sum;
last=sum;
if(i>n) break; //记得检测吃的堆数
num++;
sum=c[n--];
while(sum<=last&&i<=n) sum+=c[n--];
y+=sum;
last=sum;
}
cout<<num<<" "<<x<<" "<<y<<endl;
}
return 0;
}O - Special Elements
给定n个数，如果a[i]=sum(a[l-r])(1<=l<r<=n),那么称a[i]为一个特殊数，求这n个数中特殊数的个数。
然后将a数组前缀和处理。
枚举a[]所有区间的和，同时进行查询a[]中原来是否有这个数，如果有则加上这个数的个数即可。
#include <iostream>
#include <cstring>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int T, n, x, mx, sum[8848]={0}, cnt[8848], tmp, res;
int main(){
ios;
cin>>T;
while (T --){
res=0, mx=0;
memset(cnt, 0, sizeof(cnt));
scanf("%d",&n);
for (int i= 1;i<=n;i++){
scanf("%d",&x);
mx=max(mx,x);
sum[i]=sum[i-1]+x;
cnt[x]++;
}
for (int i=1; i < n; i ++){
for (int j=i+1; j <=n ; j ++){
tmp=sum[j]-sum[i - 1];
if(tmp>mx) break;
if (tmp<8848&&cnt[tmp] != 0) {
res+=cnt[tmp];
cnt[tmp] = 0;
}
}
}
cout<<res<<"\n";
}
return 0;
}
P - Max Sum
求最大的连续子段和，求出并输出该子段和的起始位置，记一个最大和summax,使其不断与前j个数的和比较若sum[j]>summax并记录开始与结束的位置,则使summax=sum[i];若sum[i]<0,则sum[i]=0并记录此时的位置为起始位置;此后不断循环最终得到所求结果。注意起始位置的记录。
#include<iostream>
using namespace std;
int main()
{
int n,t;
int a[100860];
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
int k=1,st=0,en=0,summax=-3000,sum=0; //记录点，最大和数
scanf("%d",&n);
for(int j=0;j<n;j++)
{
scanf("%d",&a[j]);
}
for(int j=0;j<n;j++) //不断比较阶段，注意记录起始点
{
sum+=a[j];
if(sum>summax)
{
summax=sum;
st=k;
en=j+1;
}
if(sum<0)
{
sum=0;
k=j+2;
}
}
printf("Case %d:\n%d %d %d\n",i,summax,st,en);
if(i!=t)
cout<<"\n";
}
return 0;
}
京公网安备 11010502036488号