1001
C++新特性里的to_string()函数可以将数字变为字符串,非常方便
#include <iostream>
#include <string>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
string c = to_string(a + b);
int flag = 0;
for (int i = 0; i<c.size(); ++i) {
if (c[i] == '-')
flag = 1;
cout << c[i];
if ((c.size() - 1 - i) % 3 == 0 && i != c.size() - 1&&(flag!=1||i!=0)) {
cout << ",";
}
}
return 0;
}
1002
映射法
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
float hashT[1001];
memset(hashT,0,sizeof(hashT));
int k,cnt=0;
for(int i=0;i<2;++i){
scanf("%d",&k);
int N;
float ai;
for(int j=0;j<k;++j){
scanf("%d %f",&N,&ai);
hashT[N]+=ai;
}
}
for(int i=0;i<1001;++i){
if(hashT[i]!=0)cnt++;
}
printf("%d",cnt);
for(int i=1000;i>=0;--i){
if(hashT[i]!=0.0){
printf(" %d %.1f",i,hashT[i]);
}
}
return 0;
}
1003
经典的Dijkstra算法,dist[i]数组存储起始点到i点的路径长度,w[i]存储当前路径下最多的救援队数目,num[i]存储起点到达i点的最短路径数目。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define INF 1000000
using namespace std;
/*
scatter 分散
call up hands 召集人手
*/
int main() {
int N,M,C1,C2;
int dist[510];//起点到终点的距离
int e[510][510];//边的权重
int num[510];//代表起点到终点最短路径的条数
int weight[510];//代表各个城市救援队的数目
int w[510];//代表起点到终点救援队的数目
bool visited[510];//代表该结点是否访问过
fill(e[0],e[0]+510*510,INF);
fill(dist,dist+510,INF);
scanf("%d %d %d %d",&N,&M,&C1,&C2);
for(int i=0;i<N;++i){
scanf("%d",&weight[i]);
}
int a,b,c;
for(int i=0;i<M;++i){
scanf("%d%d%d",&a,&b,&c);
e[a][b]=e[b][a]=c;
}
dist[C1]=0;
w[C1]=weight[C1];
num[C1]=1;
for(int i=0;i<N;++i){
int u=-1,minn=INF;//u存储从这个点出发可以访问的点中距离最小的
for(int j=0;j<N;++j){
if(visited[j]==false&&dist[j]<minn){
u=j;
minn=dist[j];
}
}
if(u==-1)break;//没有找到u,即图里的所有非孤立点已经搜索完毕
visited[u]=true;
for(int v=0;v<N;++v){//寻找点u的未访问过的邻接点
if(visited[v]==false&&e[u][v]!=INF){//这个点没有访问过,并且u和v之间存在边
if(dist[v]>dist[u]+e[u][v]){
dist[v]=dist[u]+e[u][v];//如果距离小,更新v到起点的距离
num[v]=num[u];
w[v]=w[u]+weight[v];
}else if(dist[v]==dist[u]+e[u][v]){
num[v]=num[u]+num[v];
if(w[u]+weight[v]>w[v]){//更新救援队数目
w[v]=w[u]+weight[v];
}
}
}
}
}
printf("%d %d",num[C2],w[C2]);
return 0;
}
1004
题目的意思是输出一棵树每一层的叶子节点数目,使用邻接表存储输入的树。用dfs遍历每一个节点,并用一个高度数组存储每一层叶子节点的数目。
#include <iostream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
vector<int> tree[100];
int book[100],max_depth=-1;
/*
pedigree 血统 家族
*/
void dfs(int index,int depth){
if(tree[index].size()==0){
book[depth]++;
max_depth=max(depth,max_depth);
return;
}
for(int i=0;i<tree[index].size();++i){
dfs(tree[index][i],depth+1);
}
}
int main() {
int n,m;
memset(book,0,sizeof(book));
scanf("%d %d",&n,&m);
for(int i=0;i<m;++i){
int id,num,son;
scanf("%d %d",&id,&num);
for(int j=0;j<num;++j){
scanf("%d",&son);
tree[id].push_back(son);
}
}
dfs(1,0);
for(int i=0;i<=max_depth;++i){
if(i==0)printf("%d",book[i]);
else printf(" %d",book[i]);
}
return 0;
}
1005
#include <iostream>
#include <stdio.h>
#include <string>
#define charToNum(x) (x-'0')
using namespace std;
int main() {
int sum = 0;
string hashT[] = { "zero","one","two","three","four","five","six","seven","eight","nine" };
string input;
cin >> input;
for (int i = 0; i<input.size(); ++i) {
sum += charToNum(input[i]);
}
string pig = to_string(sum);
bool flag = true;
for (int i = 0;i< pig.size(); ++i) {
if (flag) {
cout << hashT[charToNum(pig[i])];
flag = false;
}
else {
cout << " " << hashT[charToNum(pig[i])];
}
}
}
1006
字符串处理
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
string unlock,lock,input;
int N,t_ul_h,t_ul_m,t_ul_s,t_l_h,t_l_m,t_l_s;
int ul=999999,l=0;
cin>>N;
for(int i=0;i<N;++i){
cin>>input;
scanf("%d:%d:%d",&t_ul_h,&t_ul_m,&t_ul_s);
scanf("%d:%d:%d",&t_l_h,&t_l_m,&t_l_s);
int t_ul=t_ul_h*3600+t_ul_m*60+t_ul_s;
int t_l=t_l_h*3600+t_l_m*60+t_l_s;
if(ul>t_ul){
unlock=input;
ul=t_ul;
}
if(l<t_l){
lock=input;
l=t_l;
}
}
cout<<unlock<<" "<<lock;
return 0;
}
1007
最大连续子列和问题
递推式:
dp[i]表示以i结尾的子列的最大和
#include <iostream>
#include <algorithm>
using namespace std;
/*
indices index的复数
*/
int main() {
int N;
int dp[10010],save[10010];
dp[0]=0;
cin>>N;
int left=1,right=N,max_num=-1,temp=1;
for(int i=1;i<=N;++i){
cin>>save[i];
}
for(int i=1;i<=N;++i){
if(dp[i-1]>0){
dp[i]=dp[i-1]+save[i];
}else{
dp[i]=save[i];
temp=i;
}
if(dp[i]>max_num){
left=temp;
right=i;
max_num=dp[i];
}
}
if(max_num<0){
max_num=0;
left=1;
right=N;
}
cout<<max_num<<" "<<save[left]<<" "<<save[right];
return 0;
}
1008
??甲级
#include <iostream>
#include <stdio.h>
using namespace std;
/*
denote 代表 指代 预示
*/
int main() {
int N,sum=0,refloor=0,floor;
cin>>N;
for(int i=0;i<N;++i){
cin>>floor;
floor>refloor?sum+=(6*(floor-refloor)):sum+=(4*(refloor-floor));
sum+=5;
refloor=floor;
}
cout<<sum;
return 0;
}
1009
num数组开1000只有5分...开1001就25分了
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
double num1[1001]={0.0};
double answer[2010]={0.0};
int K1,K2,expo,cnt=0;
double coef;
scanf("%d",&K1);
for(int i=0;i<K1;++i){
scanf("%d %lf",&expo,&coef);
num1[expo]=coef;
}
scanf("%d",&K2);
for(int i=0;i<K2;++i){
scanf("%d %lf",&expo,&coef);
for(int j=0;j<=1000;++j){
answer[expo+j]+=(coef*num1[j]);
}
}
for(int i=0;i<2005;++i){
if(answer[i]!=0)cnt++;
}
cout<<cnt;
for(int i=2005;i>=0;--i){
if(answer[i]!=0)printf(" %d %.1f",i,answer[i]);
}
return 0;
}
1011
?????甲级
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
/*
trophy 纪念品,战利品
lottery 彩票
triple 三倍的
tie 平局
odd 奇数的
product 乘积
time 乘以
*/
int main() {
double w,t,l,sum=0.65;
char output[]={'W','T','L'};
int num[3];
for(int i=0;i<3;++i){
scanf("%lf%lf%lf",&w,&t,&l);
if(w>t&&w>l){
num[i]=0;
sum*=w;
}else if(t>w&&t>l){
num[i]=1;
sum*=t;
}else{
num[i]=2;
sum*=l;
}
}
for(int i=0;i<3;++i){
printf("%c ",output[num[i]]);
}
printf("%.2f",(sum-1)*2);
return 0;
}
1012
先将学生的四个成绩存储到vector中排序,然后用map存储学生的best rank,按c,m,e,a的顺序更新一个学生的rank
#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct one{
int id;
double grade;
};
struct best{
char subject;
int rank=-1;
};
vector<one> C,Math,E,A;
map<int,best> ranker;
bool compare(one a,one b){
return a.grade>b.grade;
}
int main() {
int N,M,id,c,m,e,a;
scanf("%d%d",&N,&M);
for(int i=0;i<N;++i){
scanf("%d",&id);
cin>>c>>m>>e;
C.push_back(one{id,c});
Math.push_back(one{id,m});
E.push_back(one{id,e});
A.push_back(one{id,c+m+e});
}
sort(C.begin(),C.end(),compare);
sort(Math.begin(),Math.end(),compare);
sort(E.begin(),E.end(),compare);
sort(A.begin(),A.end(),compare);
int num=1,save=1;
for(int i=0;i<E.size();++i){
if(i>=1&&E[i].grade<E[i-1].grade){
num+=save;
save=1;
}else if(i>=1)save++;
ranker[E[i].id].rank=num;
ranker[E[i].id].subject='E';
}
num=1,save=1;
for(int i=0;i<Math.size();++i){
if(i>=1&&Math[i].grade<Math[i-1].grade){
num+=save;
save=1;
}else if(i>=1)save++;
if(num<=ranker[Math[i].id].rank){
ranker[Math[i].id].rank=num;
ranker[Math[i].id].subject='M';
}
}
num=1,save=1;
for(int i=0;i<C.size();++i){
if(i>=1&&C[i].grade<C[i-1].grade){
num+=save;
save=1;
}else if(i>=1)save++;
if(num<=ranker[C[i].id].rank){
ranker[C[i].id].rank=num;
ranker[C[i].id].subject='C';
}
}
num=1,save=1;
for(int i=0;i<A.size();++i){
if(i>=1&&A[i].grade<A[i-1].grade){
num+=save;
save=1;
}else if(i>=1)save++;
if(num<=ranker[A[i].id].rank){
ranker[A[i].id].rank=num;
ranker[A[i].id].subject='A';
}
}
for(int i=0;i<M;++i){
scanf("%d",&id);
if(ranker[id].rank!=-1)
cout<<ranker[id].rank<<" "<<ranker[id].subject<<endl;
else
cout<<"N/A"<<endl;
}
}
1013
图的连通分量
#include <iostream>
#include <vector>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
bool e[1000][1000];
int N,M,K,u,v,lost;
bool once[1000];
void dfs(int node,int lost_node){
if(once[node])return;
once[node]=true;
for(int i=1;i<=N;++i){
if(i!=lost_node&&e[node][i])
dfs(i,lost_node);
}
}
int main() {
scanf("%d%d%d",&N,&M,&K);
for(int i=0;i<M;++i){
scanf("%d%d",&u,&v);
e[u][v]=true;
e[v][u]=true;
}
for(int i=0;i<K;++i){
scanf("%d",&lost);
memset(once,0,sizeof(once));
int cnt=0;
for(int j=1;j<=N;++j){
if(j!=lost&&!once[j]){
dfs(j,lost);
cnt++;
}
}
cout<<cnt-1<<endl;
}
return 0;
}
1015
素数判定+进制转换
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std;
/*
decimal 十进制的,小数的
radix 根 基数
negative 负数的 负的
*/
bool isPrime(int x){
if(x==1||x==0)return false;
for(int i=2;i*i<=x;++i){
if(x%i==0)return false;
}
return true;
}
int toDecimal(int x,int r){
string ans="";
int the_num=0;
while(x!=0){
ans+=numToChar(x%r);
x/=r;
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i){
the_num+=charToNum(ans[i])*pow(r,i);
}
return the_num;
}
int main() {
int x,radix;
while(scanf("%d",&x)){
if(x<0)return 0;
scanf("%d",&radix);
if(isPrime(x)&&isPrime(toDecimal(x,radix)))printf("Yes\n");
else printf("No\n");
}
return 0;
}
1017
将输入的时间全部转化为秒,再排序。
windows数组记录每个窗口结束工作的时间,如果一个人的到达时间小于窗口的结束工作时间,总等待时常sum增加(结束工作的时间-到达时间)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct person{
int tt;
int process;
}t[10000];
bool compare(person a,person b){
return a.tt<b.tt;
}
int main() {
int N,K,h,m,s;
double sum=0;
scanf("%d%d",&N,&K);
vector<int> windows(K,8*60*60);
for(int i=0;i<N;++i){
scanf("%d:%d:%d %d",&h,&m,&s,&t[i].process);
t[i].tt=h*3600+m*60+s;
}
int people=N;
sort(t,t+N,compare);
for(int i=0;i<N;++i){
if(t[i].tt>17*60*60){
people--;
continue;
}
int cnt=0;
for(int j=0;j<K;++j){
if(windows[cnt]>windows[j]){
cnt=j;
}
}
if(t[i].tt<=windows[cnt]){
sum+=(windows[cnt]-t[i].tt);
windows[cnt]+=t[i].process*60;
}else{
windows[cnt]=t[i].tt+t[i].process*60;
}
}
printf("%.1f",sum/(60*people));
return 0;
}
1018
Dijkstra+dfs
本题主要的坑在于后面节点的单车不能移送给前面的节点,导致第五,第七个测试点无法通过,解决方法是用Dfs回溯所有的节点。
#include <iostream>
#include <stack>
#include <map>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define INF 1000000
using namespace std;
int minNeed=INF,minBack=INF;
int C,N,S,M,dist[510],e[510][510],weight[510];
bool visit[510];
vector<int> preway[510];
vector<int> path,temppath;
void Dfs(int v){
temppath.push_back(v);
if(v==0){
int need=0,back=0;
for(int i=temppath.size()-1;i>=0;--i){
int pos=temppath[i];
if(weight[pos]>0){
back+=weight[pos];
}else{
if(back>(0-weight[pos])){
back+=weight[pos];
}else{
need+=(0-weight[pos]-back);
back=0;
}
}
}
if(need<minNeed){
minNeed=need;
minBack=back;
path=temppath;
}else if(need==minNeed&&back<minBack){
minBack=back;
path=temppath;
}
temppath.pop_back();
return;
}
for(int i=0;i<preway[v].size();++i){
Dfs(preway[v][i]);//检索一条路
}
temppath.pop_back();
}
int main() {
fill(e[0],e[0]+510*510,INF);
fill(dist,dist+510,INF);
scanf("%d %d %d %d",&C,&N,&S,&M);
for(int i=1;i<=N;++i){
scanf("%d",&weight[i]);
weight[i]=weight[i]-C/2;
}
int a,b,c;
for(int i=1;i<=M;++i){
scanf("%d %d %d",&a,&b,&c);
e[a][b]=e[b][a]=c;
}
dist[0]=0;
for(int i=0;i<=N;++i){
int u=-1,minn=INF;
for(int j=0;j<=N;++j){
if(dist[j]<minn&&!visit[j]){
u=j;
minn=dist[j];
}
}
if(u==-1)break;
visit[u]=true;
for(int v=0;v<=N;++v){
if(!visit[v]&&e[u][v]!=INF){
if(e[u][v]+dist[u]<dist[v]){
dist[v]=dist[u]+e[u][v];
preway[v].clear();
preway[v].push_back(u);
}else if(e[u][v]+dist[u]==dist[v]){
preway[v].push_back(u);
}
}
}
}
Dfs(S);
printf("%d 0",minNeed);
for(int i=path.size()-2;i>=0;--i){
printf("->%d",path[i]);
}
printf(" %d",minBack);
return 0;
}
1019
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
/*
notation 记号
*/
int main() {
int N, base;
vector<string> save;
cin >> N >> base;
while (N != 0) {
save.push_back(to_string(N%base));
N /= base;
}
bool isOK = true;
for (int i = 0; i < save.size() / 2; ++i) {
if (save[i] != save[save.size() - i - 1])isOK = false;
}
isOK ? cout << "Yes" << endl : cout << "No" << endl;
bool flag = true;
reverse(save.begin(), save.end());
for (int i = 0; i < save.size(); ++i) {
if (flag) {
cout << save[i];
flag = false;
}
else {
cout <<" "<< save[i];
}
}
return 0;
}
1021
这是只有23分的代码,第三个测试点超时了,估计是进行了多次深搜的缘故,英国可以用一次深搜解决不过我太懒了
#include <iostream>
#include <vector>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
/*
acyclic 非循环的 非周期的
*/
bool e[10001][10001];
int N,a,b,circle=0,deepest=-1;
bool visited[10001];
int highest[10001];
void dfs(int node){
visited[node]=true;
for(int i=1;i<=N;++i){
if(e[node][i]&&!visited[i])dfs(i);
}
}
void DFS(int root,int node,int depth){
if(visited[node]){
return;
}
highest[root]=max(highest[root],depth);
visited[node]=true;
deepest=max(deepest,depth);
for(int i=1;i<=N;++i){
if(e[node][i])DFS(root,i,depth+1);
}
visited[node]=false;
}
int main() {
memset(highest,0,sizeof(highest));
cin>>N;
for(int i=0;i<N-1;++i){
cin>>a>>b;
e[a][b]=e[b][a]=true;
}
for(int i=1;i<=N;++i){
if(!visited[i]) {
dfs(i);
circle++;
}
}
memset(visited,0,sizeof(visited));
if(circle>=2){
printf("Error: %d components",circle);
return 0;
}
for(int i=1;i<=N;++i){
DFS(i,i,1);
}
for(int i=1;i<=N;++i){
if(highest[i]==deepest)cout<<i<<endl;
}
return 0;
}
1023
大整数加减进位要注意呀
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std;
/*
duplication 重复
permutation 排序
*/
int main() {
int mapper[9];
fill(mapper,mapper+9,0);
string a;
cin>>a;
for(int i=0;i<a.size();++i){
mapper[charToNum(a[i])]++;
}
reverse(a.begin(),a.end());
bool flag=false,isOk=true;
for(int i=0;i<a.size();++i){
int t=charToNum(a[i])*2;
if(flag){
t+=1;
flag=false;
}
if(t>9)flag=true;
t%=10;
a[i]=numToChar(t);
if(--mapper[t]<0)isOk=false;
}
if(flag)a+='1';
isOk&&!flag?cout<<"Yes"<<endl:cout<<"No"<<endl;
reverse(a.begin(),a.end());
cout<<a<<endl;
return 0;
}
1024
大整数加减
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std;
/*
palindromic 复发的 再发的
via 通过 经过
*/
string add(string x,string y){
string ans="";
int sum=0;
bool flag=false;
for(int i=0;i<x.size();++i){
if(flag){
sum+=1;
flag=false;
}
sum+=charToNum(x[i])+charToNum(y[i]);
if(sum>9){
sum%=10;
flag=true;
}
ans+=numToChar(sum);
sum=0;
}
if(flag)ans+='1';
reverse(ans.begin(),ans.end());
return ans;
}
bool isPalindromic(string x){
string y=x;
reverse(x.begin(),x.end());
return x==y;
}
int main() {
string input;
int step,cnt=0;
cin>>input>>step;
while(cnt++<step&&!isPalindromic(input)) {
string temp=input;
reverse(temp.begin(),temp.end());
input=add(input,temp);
}
cout<<input<<endl<<cnt-1;
return 0;
}
1025
含有并列的排名如何排序
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
simultaneously 同时地 一齐的
testee 考试者
*/
struct testee{
string id;
int grade;
int local_rank;
int rank;
int location;
};
vector<testee> save;
bool cmp(testee a,testee b){
return a.grade!=b.grade?a.grade>b.grade:a.id<b.id;
}
int main() {
int N,K;
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%d",&K);
vector<testee> atemp;
for(int j=0;j<K;++j){
testee temp;
cin>>temp.id>>temp.grade;
temp.location=i+1;
atemp.push_back(temp);
}
sort(atemp.begin(),atemp.end(),cmp);
int cnt=1,saver=1;
atemp[0].local_rank=1;
for(int i=1;i<atemp.size();++i){
if(atemp[i].grade!=atemp[i-1].grade){
cnt+=saver;
saver=1;
}else saver++;
atemp[i].local_rank=cnt;
}
save.insert(save.end(),atemp.begin(),atemp.end());
}
sort(save.begin(),save.end(),cmp);
int cnt=1,saver=1;
save[0].rank=1;
for(int i=1;i<save.size();++i){
if(save[i].grade!=save[i-1].grade){
cnt+=saver;
saver=1;
}else saver++;
save[i].rank=cnt;
}
cout<<save.size()<<endl;
for(int i=0;i<save.size();++i){
cout<<save[i].id<<" "<<save[i].rank<<" "<<save[i].location<<" "<<save[i].local_rank<<endl;
}
return 0;
}
1027
十进制转13进制
#include <iostream>
#include <string>
using namespace std;
string trans(int x){
string ans="";
char hashT[]={'A','B','C'};
int a=x/13;
int b=x%13;
if(a>=0&&a<10)ans+=(a+'0');
else if(a>=10)ans+=hashT[a-10];
if(b>=0&&b<10)ans+=(b+'0');
else if(b>=10)ans+=hashT[b-10];
return ans;
}
int main() {
int r,g,b;
cin>>r>>g>>b;
cout<<"#"<<trans(r)<<trans(g)<<trans(b);
return 0;
}
1029
双指针法,第二行不用存储,在线处理即可
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int main() {
int N,M,temp,flag=0;
int count=0;
vector<int> save;
scanf("%d",&N);
save.resize(N);
for(int i=0;i<N;++i){
scanf("%d",&save[i]);
}
scanf("%d",&M);
int mid=(M+N+1)/2;
for(int i=0;i<M;++i){
scanf("%d",&temp);
bool ud=false;
while(temp>save[flag]&&flag<N&&count<mid){
if(++count==mid){
cout<<save[flag];
}
flag++;
}
if(++count==mid){
cout<<temp;
}
}
while(flag<N){
if(++count==mid){
cout<<save[flag];
}
flag++;
}
return 0;
}
1030
Dijkstra+dfs
1018的简化版,把点权改成了边权
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 1000000
using namespace std;
int N,M,S,D,min_cost=INF;
int dist[510],weight[510][510],e[510][510];
bool visit[510];
vector<int> save[510];
vector<int> path,temppath;
void Dfs(int v){
temppath.push_back(v);
if(v==S){
int cost=0;
for(int i=0;i<temppath.size()-1;++i)
cost+=weight[temppath[i]][temppath[i+1]];
if(cost<min_cost){
min_cost=cost;
path=temppath;
}
temppath.pop_back();//回溯
return;
}
for(int i=0;i<save[v].size();++i){
Dfs(save[v][i]);
}
temppath.pop_back();
}
int main() {
fill(dist,dist+510,INF);
fill(e[0],e[0]+510*510,INF);
scanf("%d%d%d%d",&N,&M,&S,&D);
int a,b,c,d;
for(int i=0;i<M;++i){
scanf("%d%d%d%d",&a,&b,&c,&d);
e[a][b]=e[b][a]=c;
weight[a][b]=weight[b][a]=d;
}
dist[S]=0;
for(int i=0;i<N;++i){
int u=-1,minn=INF;
for(int j=0;j<N;++j){
if(!visit[j]&&dist[j]<minn){
u=j;
minn=dist[j];
}
}
if(u==-1)break;
visit[u]=true;
for(int v=0;v<N;++v){
if(e[u][v]!=INF&&!visit[v]){
if(e[u][v]+dist[u]<dist[v]){
dist[v]=e[u][v]+dist[u];
save[v].clear();
save[v].push_back(u);
}else if(e[u][v]+dist[u]==dist[v]){
save[v].push_back(u);
}
}
}
}
Dfs(D);
for(int i=path.size()-1;i>=0;--i){
printf("%d ",path[i]);
}
printf("%d",dist[D]);
printf(" %d",min_cost);
return 0;
}
1031
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
/*
vertical 竖直的 垂直的
*/
int main() {
string input;
cin>>input;
int k,t=3;
int maxlen=0;
for(;t<=input.size();++t){
for(k=0;k<=t;k++){
if(input.length()+2==2*k+t){
maxlen=max(maxlen,k);
}
}
}
t=input.size()+2-2*maxlen;
for(int i=0;i<maxlen-1;++i){
cout<<input[i];
for(int j=0;j<t-2;++j)cout<<" ";
cout<<input[input.length()-i-1]<<endl;
}
for(int i=maxlen-1;i<=input.length()-maxlen;++i)cout<<input[i];
return 0;
}
1032
简单的链表题
#include <iostream>
#include <algorithm>
#include <string.h>
#define INF 100000
using namespace std;
/*
suffix 后缀 词尾
*/
int main() {
int add[INF];
int head1,head2,N,temp,next;
bool visit[INF];
memset(visit,0,sizeof(visit));
char alpha;
cin>>head1>>head2>>N;
for(int i=0;i<N;++i){
cin>>temp>>alpha>>next;
add[temp]=next;
}
while(head1!=-1){
visit[head1]=true;
head1=add[head1];
}
while(head2!=-1){
if(!visit[head2]){
visit[head2]=true;
head2=add[head2];
}else break;
}
if(head2!=-1)
printf("%05d",head2);
else
printf("-1");
return 0;
}
1035
姥姥日常挖坑。。。注意account单复数
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
/*
generate 形成 造成
*/
struct line{
string id;
string pwd;
}lines[1000];
bool flag[1000];
int main() {
int N,cnt=0;
fill(flag,flag+1000,0);
cin>>N;
for(int i=0;i<N;++i){
cin>>lines[i].id>>lines[i].pwd;
for(int j=0;j<lines[i].pwd.size();++j){
if(lines[i].pwd[j]=='1'){
lines[i].pwd[j]='@';
flag[i]=true;
}else if(lines[i].pwd[j]=='0'){
lines[i].pwd[j]='%';
flag[i]=true;
}else if(lines[i].pwd[j]=='l'){
lines[i].pwd[j]='L';
flag[i]=true;
}else if(lines[i].pwd[j]=='O'){
lines[i].pwd[j]='o';
flag[i]=true;
}
}
if(flag[i])cnt++;
}
if(cnt){
cout<<cnt<<endl;
for(int i=0;i<N;++i){
if(flag[i])cout<<lines[i].id<<" "<<lines[i].pwd<<endl;
}
}else if(N!=1){
printf("There are %d accounts and no account is modified\n",N);
}else{
printf("There is 1 account and no account is modified\n");
}
return 0;
}
1036
怕不是假的甲级
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*
distinct 不同的,明显的
*/
int main() {
int N;
string name,id,name_man,id_man,name_girl,id_girl;
char gender;
int grade,min_man=101,max_girl=-1;
cin>>N;
for(int i=0;i<N;++i){
cin>>name>>gender>>id>>grade;
if(gender=='F'&&grade>max_girl){
max_girl=grade;
name_girl=name;
id_girl=id;
}else if(gender=='M'&&grade<min_man){
min_man=grade;
name_man=name;
id_man=id;
}
}
if(max_girl!=-1){
cout<<name_girl<<" "<<id_girl<<endl;
}else{
cout<<"Absent"<<endl;
}
if(min_man!=101){
cout<<name_man<<" "<<id_man<<endl;
}else{
cout<<"Absent"<<endl;
}
if(min_man!=101&&max_girl!=-1){
cout<<max_girl-min_man<<endl;
}else{
puts("NA");
}
return 0;
}
1037
将正数与负数分开存储,然后贪心
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
bonus 奖金
exceed 超过 超越
*/
bool cmp(int a,int b){
return a>b;
}
int main() {
int N,K,temp,sum=0,flag1=0,flag2=0;
vector<int> coupon_1,coupon_2,product_1,product_2;
cin>>N;
for(int i=0;i<N;++i){
cin>>temp;
if(temp>0)
coupon_1.push_back(temp);
else
coupon_2.push_back(temp);
}
cin>>K;
for(int i=0;i<K;++i){
cin>>temp;
if(temp>0)
product_1.push_back(temp);
else
product_2.push_back(temp);
}
sort(coupon_1.begin(),coupon_1.end(),cmp);
sort(product_1.begin(),product_1.end(),cmp);
sort(coupon_2.begin(),coupon_2.end());
sort(product_2.begin(),product_2.end());
for(;flag1<coupon_1.size()&&flag2<product_1.size();){
sum+=coupon_1[flag1++]*product_1[flag2++];
}
flag1=0;flag2=0;
for(;flag1<coupon_2.size()&&flag2<product_2.size();){
sum+=coupon_2[flag1++]*product_2[flag2++];
}
cout<<sum;
return 0;
}
1038
这道题直接sort是不行的,要比较两个字符串谁在前面,只需将两者分别加起来比较就行。可以用erase方法删除首元素的0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
segment 部分
*/
bool cmp(string a,string b){
return a+b<b+a;//这波操作真的牛逼
}
int main() {
int N;
string temp,output;
cin>>N;
vector<string> input;
for(int i=0;i<N;++i){
cin>>temp;
input.push_back(temp);
}
sort(input.begin(),input.end(),cmp);
for(int i=0;i<N;++i)
output+=input[i];
while(output.length()!=1&&output[0]=='0'){
output.erase(output.begin());
}
cout<<output<<endl;
return 0;
}
1040
回文数的动态规划问题
dp[i][j]=1代表i~j为回文字符串
dp[i][j]=0代表i~j不是回文字符串
如果str[i]==str[j],dp[i][j]=dp[i+1][j-1]
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*
symmetric 相称的 均衡的
*/
int main() {
int max_num=1;
string str;
getline(cin,str);
int dp[1010][1010];
for(int i=0;i<str.length();++i){
dp[i][i]=1;
if(i<str.size()-1&&str[i]==str[i+1]){
dp[i][i+1]=1;
max_num=2;
}
}
for(int L=3;L<=str.length();++L){
for(int i=0;i+L-1<str.length();++i){
int j=i+L-1;
if(str[i]==str[j]&&dp[i+1][j-1]==1)dp[i][j]=1;
else dp[i][j]=0;
if(dp[i][j])max_num=L;
}
}
cout<<max_num;
return 0;
}
1041
hash散列
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int main() {
int ascii[100000],N;
vector<int> save;
memset(ascii,0,sizeof(ascii));
cin>>N;
for(int i=0;i<N;++i){
int temp;
cin>>temp;
ascii[temp]++;
save.push_back(temp);
}
for(int i=0;i<save.size();++i){
if(ascii[save[i]]==1){
cout<<save[i]<<endl;
return 0;
}
}
cout<<"None"<<endl;
return 0;
}
1046
数组的每一项保存第一个node到这一项的node的距离,当要求两点距离时,只需将右边的距离减去左边的距离即可
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int main() {
int N,e[100000],sum=0,temp;
e[0]=0;
cin>>N;
for(int i=1;i<=N;++i){
cin>>temp;
sum+=temp;
e[i]=e[i-1]+temp;
}
int K,node1,node2;
cin>>K;
for(int i=0;i<K;++i){
cin>>node1>>node2;
if(node1>node2)swap(node1,node2);
int len=e[node2-1]-e[node1-1];
cout<<(len>sum-len?sum-len:len)<<endl;
}
return 0;
}
1047
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
/*
sake 缘故 理由
*/
int main() {
int N,K,C,id;
cin>>N>>K;
vector<string> save[2510];
string name;
for(int i=0;i<N;++i){
cin>>name>>C;
for(int i=0;i<C;++i){
cin>>id;
save[id].push_back(name);
}
}
for(int i=1;i<=K;++i){
sort(save[i].begin(),save[i].end());
printf("%d %d\n",i,save[i].size());
for(int j=0;j<save[i].size();++j){
printf("%s\n",save[i][j].c_str());
}
}
return 0;
}
1048
#include <iostream>
#include <string.h>
using namespace std;
int main() {
int N,M,a[1001],input;;
cin>>N>>M;
memset(a,0,sizeof(a));
for(int i=0;i<N;++i){
cin>>input;
a[input]++;
}
for(int i=0;i<1001;++i){
if(a[i]){
a[i]--;
if(M>i&&a[M-i]!=0){
cout<<i<<" "<<M-i;
return 0;
}
}
}
cout<<"No Solution";
return 0;
}
1052
链表排序题
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
/*
adjacent 相邻的
*/
struct node{
int data;
int next;
int add;
};
bool cmp(node a,node b){
return a.data<b.data;
}
int main() {
node nodes[100010];
vector<node> output;
int N,head,add,next,data;
scanf("%d %d",&N,&head);
for(int i=0;i<N;++i){
scanf("%d %d %d",&add,&data,&next);
nodes[add]={data,next,add};
}
while(head!=-1){
output.push_back(nodes[head]);
head=nodes[head].next;
}
if(output.size()!=0){
sort(output.begin(),output.end(),cmp);
printf("%d %05d\n",output.size(),output[0].add);
}
else{
printf("0 -1");
return 0;
}
for(int i=0;i<output.size()-1;++i){
printf("%05d %d %05d\n",output[i].add,output[i].data,output[i+1].add);
}
printf("%05d %d -1",output[output.size()-1].add,output[output.size()-1].data);
return 0;
}
1054
stl map的使用
#include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
/*
pixel 像素
proportional 成比例的
dominant 占优势的
resolution 分辨率 决心
*/
map<int,int> save;
int main() {
int N,M,pixel,dominant;
scanf("%d %d",&N,&M);
for(int i=0;i<N;++i){
for(int j=0;j<M;++j){
scanf("%d",&pixel);
if(++save[pixel]>(N*M/2))dominant=pixel;
}
}
cout<<dominant<<endl;
return 0;
}
1076
图的bfs,关键是stl中queue的使用,首先先把待查询的node入队,然后将node出队,把与node相连的节点依次入队,直到队列为空为止。
#include <iostream>
#include <queue>
#include <string.h>
#include <stdio.h>
using namespace std;
/*
query 询问
trigger 扳机
*/
struct node{
int id;
int level;
};
int N,L,K;
vector<int> graph[1010];
int bfs(node query){
bool vis[1010];
memset(vis,0,sizeof(vis));
queue<node> q;
q.push(query);
vis[query.id]=true;
int cnt=0;
while(!q.empty()){
node top=q.front();
q.pop();
for(int i=0;i<graph[top.id].size();++i){
if(vis[graph[top.id][i]]==false&&top.level<L){
vis[graph[top.id][i]]=true;
node temp={graph[top.id][i],top.level+1};
q.push(temp);
cnt++;
}
}
}
return cnt;
}
int main() {
int temp,query;
cin>>N>>L;
for(int i=1;i<=N;++i){
int num;
cin>>num;
for(int j=0;j<num;++j){
cin>>temp;
graph[temp].push_back(i);
}
}
cin>>K;
for(int i=0;i<K;++i){
cin>>query;
node temp={query,0};
printf("%d\n",bfs(temp));
}
return 0;
}
1078
哈希表的平方探测,关键是index=(x+step*step)%M
将step的平方加上原来的下标再取余size,当step的值已经达到size时终止循环
#include <iostream>
#include <string.h>
using namespace std;
/*
collision 冲突
quadratic 二次的
*/
int M,N,input;
bool hashT[10010];
bool is_prime(int x){
if(x<=1)return false;
for(int i=2;i*i<=x;++i){
if(x%i==0)return false;
}
return true;
}
void insert(int x){
for(int step=0;step<M;step++){
int index=(x+step*step)%M;
if(hashT[index]==0){
hashT[index]=1;
cout<<index;
return;
}
}
cout<<"-";
}
int main() {
memset(hashT,0,sizeof(hashT));
cin>>M>>N;
while(!is_prime(M))M++;
for(int i=0;i<N;++i){
cin>>input;
if(i!=0)cout<<" ";
insert(input);
}
return 0;
}
1079
给定一棵树,从根节点开始dfs
另外pow()比自己用for快
#include <iostream>
#include <map>
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
/*
increment 增长
*/
int N;
double sum=0,P,r;
vector<int> graph[100010];
map<int,int> retailers;
void dfs(int node,int cnt){
if(graph[node].size()==0){
double add=1+r/100;
sum+=retailers[node]*P*pow(add,cnt);
return;
}
for(int i=0;i<graph[node].size();++i){
dfs(graph[node][i],cnt+1);
}
}
int main() {
scanf("%d%lf%lf",&N,&P,&r);
int k,temp;
for(int i=0;i<N;++i){
scanf("%d",&k);
for(int j=0;j<k;++j){
scanf("%d",&temp);
graph[i].push_back(temp);
}
if(k==0){
scanf("%d",&temp);
retailers[i]=temp;
}
}
dfs(0,0);
printf("%.1f",sum);
return 0;
}
1094
求generation最大的一代,先用二维数组存储这棵树,然后从根节点开始dfs
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int N,M,levels[110];
vector<int> tree[110];
void dfs(int node,int level){
levels[level]++;
if(tree[node].size()==0) return;
for(int i=0;i<tree[node].size();++i){
dfs(tree[node][i],level+1);
}
}
int main() {
int id,k,temp,max_level=1,max_size=1;
memset(levels,0,sizeof(levels));
scanf("%d %d",&N,&M);
for(int i=0;i<M;++i){
scanf("%d %d",&id,&k);
for(int j=0;j<k;++j){
scanf("%d",&temp);
tree[id].push_back(temp);
}
}
dfs(1,1);
for(int i=1;i<=100;++i){
if(levels[i]>max_size){
max_size=levels[i];
max_level=i;
}
}
cout<<max_size<<" "<<max_level;
return 0;
}
1145
哈希表的二次方探测法
注意检索的时候,如果,要提前return
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int MSize,N,M;
int hashT[10010];
double cnt=0;
bool vis[10010];
bool is_prime(int x){
if(x<=1)return false;
for(int i=2;i*i<=x;++i){
if(x%i==0)return false;
}
return true;
}
void insert(int x){
for(int step=0;step<MSize;step++){
int index=(x+step*step)%MSize;
if(!vis[index]){
vis[index]=true;
hashT[index]=x;
return;
}
}
printf("%d cannot be inserted.\n",x);
}
void find(int x){
for(int step=0;step<=MSize;step++){
int index=(x+step*step)%MSize;
cnt++;
if(hashT[index]==x||vis[index]==false){
return;
}
}
}
int main() {
memset(vis,0,sizeof(vis));
int input;
cin>>MSize>>N>>M;
while(!is_prime(MSize))MSize++;
for(int i=0;i<N;++i){
cin>>input;
insert(input);
}
for(int i=0;i<M;++i){
cin>>input;
find(input);
}
printf("%.1f",cnt/M);
return 0;
}