A.复读
这题只需判断这个字符串是否是第一次出现,如果是就加到res中,否则就跳过
#include<iostream>
#include<unordered_map>
using namespace std;
string res;
unordered_map<string,bool>h;
int main()
{
string s;
int k=0;
while(cin>>s,s!="0")
{
if(h[s]==false)
{
res+=s;
h[s]=true;
}
}
cout<<res<<endl;
return 0;
}
B.时钟
对于这个题我们可以先求出一天内有多少个好时刻,
#include<iostream>
using namespace std;
int res=0;
int main()
{
for(int i=0;i<=1440;i++)
{
int x=i/60;
int y=i%60;
if(x<10){
int a=x;
int b=y/10;
int c=y%10;
if(a-b==b-c) res++;
}else{
int a=x/10;
int b=x%10;
int c=y/10;
int d=y%10;
if(a-b==b-c&&b-c==c-d) res++;
}
}
cout<<res<<endl;
return 0;
}
运行上面程序得出一天一共有39个好时刻
第二步 算出总分钟mod 1440 之中有多少个好时刻
#include<iostream>
using namespace std;
int res=0;
int m;
int main()
{
cin>>m;
int day=m/1440;
m=m%1440;
for(int i=0;i<=m;i++)
{
int x=i/60;
int y=i%60;
if(x<10){
int a=x;
int b=y/10;
int c=y%10;
if(a-b==b-c) res++;
}else{
int a=x/10;
int b=x%10;
int c=y/10;
int d=y%10;
if(a-b==b-c&&b-c==c-d) res++;
}
}
cout<<res+day*39<<endl;
return 0;
}
C.平等的交易
这个题目认真读题之后很简单,贪心下就ok了,用sort排序,题目总的时间复杂度不能操过$O(n*logn)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n,w,s[N];
int res=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
cin>>w;
sort(s,s+n);
if(s[n-1]==0) res=0; //如果最后他能买的只有零价值的商品,那他不能和任何物品交换.res=0;
else {
for(int i=n-1;i>=0;i--) //找到他所能买的最大价值的物品;
{
if(s[i]<=w) {
w=s[i];
break;
}
}
int sum=0;
int cnt=0;
for(int i=0;i<n;i++) //从最小价值的开始枚举,买的个数尽量多
{
sum+=s[i];
if(sum>w) break;
cnt++;
}
res=cnt;
}
cout<<res<<endl;
return 0;
}
D.清洁工
#include<iostream>
#include<cstring>
#include<vector>
//第一分钟是初始点,直到倒数第二个点,最后一个点不考虑
using namespace std;
const int N = 55;
string sg;
int sx,sy; //初始坐标,但不是数组中的下标 需要转化下
int n,m;//数组的大小和字符串长度
//上 右 下 左 转化关系对应于数组坐标的变换
int dx[4]= { -1, 0, 1 ,0};
int dy[4]= { 0, 1, 0 ,-1};
vector<int>s[N][N];
int res[N][N];
void turn(int x,int y)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==x&&j==y) s[i][j].push_back(0);
else s[i][j].push_back(s[i][j].back()+1);
}
}
}
int main() {
cin>>n>>m>>sx>>sy;
cin>>sg;
int t=sy;
sy=sx;
sx=n-t+1;
//初始坐标
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==sx&&j==sy) s[i][j].push_back(0);
else s[i][j].push_back(1);
}
for(int i=0;i<sg.size()-1;i++)
{
if(sg[i]=='N')
{
sx+=dx[0],sy+=dy[0];
}
else if(sg[i]=='E'){
sx+=dx[1],sy+=dy[1];
}
else if(sg[i]=='S')
{
sx+=dx[2],sy+=dy[2];
}
else sx+=dx[3],sy+=dy[3];
turn(sx,sy);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int sum=0;
for(int k=0;k<s[i][j].size();k++)
{
sum+=s[i][j][k];
}
res[i][j]=sum;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<res[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
E.树的变迁
这个题目是有关倒序并查集(其实就是倒着来处理数据)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
//存下输出的答案
vector<int>res;
struct node{
int a;
int b;
}nums[N];
struct options{
int k;
int u;
int val;
}option[N];
int n,m;//n个节点,m个操作
int sum[N],f[N];//存下节点//存下每个节点的父节点是什么
bool st[N];//判断这条边是否被断开
int back[N];
//find()函数模板
int find(int x)
{
return (x==f[x])?x:f[x]=find(f[x]);
}
//合并函数模板
void merge(int a,int b)
{
int x=find(a);
int y=find(b);
if(x!=y)
{
f[x]=y;
sum[y]+=sum[x];
}
}
int main() {
cin >> n >> m;
//存下节点
for (int i = 1; i <= n; i++) {
cin >> sum[i];
}
//存下n-1行的边
for (int i = 1; i < n; i++) {
cin >> nums[i].a >> nums[i].b;
}
//存下每个操作
for (int i = 1; i <= m; i++) {
int k;
cin >> k;
option[i].k = k;
if (k == 1) {
int x;
cin >> x;
option[i].u=x;
st[x] = true;
} else if (k == 2) {
//存下每次操作的改变之前的值
int u, val;
cin >> u >> val;
option[i].u = u;
option[i].val = val;
back[i]=sum[u];
sum[u]=val;
} else {
cin>>option[i].u;
}
}
//上面的操作已经存下来了,接下来直接倒序遍历
for (int i = 1; i <= n; i++) f[i]=i;
//连起来没有断开的边
for(int i=1;i<n;i++){
if(st[i]==false) {
merge(nums[i].a,nums[i].b);
}
}
//倒序操作
for(int i=m;i>=1;i--)
{
if(option[i].k==1)
{//连起来断开的边
int u=option[i].u;
merge(nums[u].a,nums[u].b);
}
else if(option[i].k==2){
int u=option[i].u;
int val=option[i].val;
int ff=find(u);
sum[ff]-=val;
sum[ff]+=back[i];
}
else{
int u=find(option[i].u);
res.push_back(sum[u]);
}
}
reverse(res.begin(),res.end());
for(int i=0;i<res.size();i++)
{
cout<<res[i]<<endl;
}
return 0;
}
F.白色旅人
这题等我学完算法提高课再去补
E的源码在哪看的
就是别人的代码
我写的呀