赞
踩
#include <stdio.h>
int main(){
int a,b,sum=0,count=0;
char tmp[15];
scanf("%d%d",&a,&b);
sum=a+b;
if(sum<0){
printf("-");
sum=-sum;
}
if(sum==0){
count=1;
tmp[0]='0';
}
for(int i=0;i<10;i++){
if(sum!=0){
tmp[i]=(char)(sum%10+'0');
sum/=10;
count++;
}
}
for(int i=count-1;i>=0;i--){
printf("%c",tmp[i]);
if(i>0&&i%3==0) //重点语句
printf(",");
}
printf("\n");
return 0;
}
#include <stdio.h>
int main(){
double m,a[1001]={0};
int k,k1,k2,count=0;
scanf("%d",&k1);
for(int i=0;i<k1;i++){
scanf("%d%lf",&k,&m);
a[k]+=m;
}
scanf("%d",&k2);
for(int i=0;i<k2;i++){
scanf("%d%lf",&k,&m);
a[k]+=m;
}
for(int i=0;i<=1000;i++){
if(a[i]!=0)
count++;
}
printf("%d",count);
for(int i=1000;i>=0;i--){
if(a[i]!=0){
if(count>0)
printf(" ");
printf("%d %.1f",i,a[i]);
count--;
}
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxv=505;
const int INF=1000000000;
int w[maxv],d[maxv],num[maxv];
int n,m,c1,c2,G[maxv][maxv],weight[maxv];
bool vis[maxv]={false};
void Dijkstra(int s){
fill(d,d+maxv,INF);
memset(num,0,sizeof(num));
memset(w,0,sizeof(w));
d[s]=0;
w[s]=weight[s];
num[s]=1;
for(int i=0;i<n;i++){
int u=-1,min=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&d[j]<min){
u=j;
min=d[j];
}
}
if(u==-1)
return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
w[v]=w[u]+weight[v];
num[v]=num[u];
}else if(d[u]+G[u][v]==d[v]){
if(w[v]<w[u]+weight[v]){
w[v]=w[u]+weight[v];
}
num[v]+=num[u];
}
}
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&c1,&c2);
int u,v;
fill(G[0],G[0]+maxv*maxv,INF);
for(int i=0;i<n;i++){
scanf("%d",&weight[i]);
}
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
scanf("%d",&G[u][v]);
G[v][u]=G[u][v];
}
Dijkstra(c1);
printf("%d %d\n",num[c2],w[c2]);
return 0;
}
方法一:DFS(深度优先搜索)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> G[110];
int leaf[110]={0};
int max_h=1;
void DFS(int index,int h){
max_h=max(h,max_h);
if(G[index].size()==0){
leaf[h]++;
return;
}
for(int i=0;i<G[index].size();i++){
DFS(G[index][i],h+1);
}
}
int main(){
int n,m,parent,k,child;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&parent,&k);
for(int j=0;j<k;j++){
scanf("%d",&child);
G[parent].push_back(child);
}
}
DFS(1,1);
for(int i=1;i<=max_h;i++){
printf("%d",leaf[i]);
if(i<max_h)
printf(" ");
}
printf("\n");
return 0;
}
方法二:BFS(广度优先搜索)
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> G[110]; //用来存放树的各个子结点
int leaf[110]={0};
int h[110]={0};
int maxh=0;
void BFS(){
queue<int> q;
q.push(1);
while(!q.empty()){
int id=q.front();
q.pop();
maxh=max(maxh,h[id]);
if(G[id].size()==0){
leaf[h[id]]++;
}
for(int i=0;i<G[id].size();i++){
h[G[id][i]]=h[id]+1;
q.push(G[id][i]);
}
}
}
int main(){
int n,m,parent,k,child;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&parent,&k);
for(int j=0;j<k;j++){
scanf("%d",&child);
G[parent].push_back(child);
}
}
h[1]=1;
BFS();
for(int i=1;i<=maxh;i++){
printf("%d",leaf[i]);
if(i<maxh)
printf(" ");
}
printf("\n");
return 0;
}
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int sum=0,temp[10]={0},k=0;
string s[10]={"zero","one","two","three","four","five","six","seven","eight","nine"};
string str;
cin>>str;
for(int i=0;i<str.length();i++){
sum+=str[i]-'0';
}
if(sum==0){
cout<<s[0]<<endl;
return 0;
}
for(int i=0;i<10;i++){
if(sum!=0){
temp[i]=sum%10;
sum/=10;
k++;
}
}
for(int i=k-1;i>=0;i--){
cout<<s[temp[i]];
if(i>0)
cout<<" ";
}
return 0;
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct student{
string id,first,last;
};
vector<student> temp;
bool cmp1(student a,student b){
return a.first<b.first;
}
bool cmp2(student a,student b){
return a.last>b.last;
}
int main(){
int m;
cin>>m;
temp.resize(m);
for(int i=0;i<m;i++){
cin>>temp[i].id>>temp[i].first>>temp[i].last;
}
sort(temp.begin(),temp.end(),cmp1);
cout<<temp[0].id<<" ";
sort(temp.begin(),temp.end(),cmp2);
cout<<temp[0].id<<endl;
return 0;
}
#include <stdio.h>
const int maxn=10010;
int A[maxn],dp[maxn],s[maxn]={0};
int main(){
int n,flag=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&A[i]);
if(A[i]>=0)
flag=1;
}
if(flag==0){
printf("0 %d %d\n",A[0],A[n-1]);
return 0;
}
//边界
dp[0]=A[0];
for(int i=1;i<n;i++){
//状态转移方程
if(dp[i-1]+A[i]>A[i]){
dp[i]=dp[i-1]+A[i];
s[i]=s[i-1];
}else{
dp[i]=A[i];
s[i]=i;
}
}
int k=0;
for(int i=1;i<n;i++){
if(dp[i]>dp[k]){
k=i;
}
}
printf("%d %d %d\n",dp[k],A[s[k]],A[k]);
return 0;
}
#include <stdio.h>
int main(){
int n,a[105],sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(i==0){
sum=5+6*a[i];
}
else{
if(a[i]>=a[i-1]){
sum=sum+6*(a[i]-a[i-1])+5;
}else{
sum=sum+4*(a[i-1]-a[i])+5;
}
}
}
printf("%d\n",sum);
return 0;
}
#include <stdio.h>
struct Poly{
int k; //指数
double c; //系数
}p[1001];
double flag[2001];
int main(){
int k1,k2,temp=0;
scanf("%d",&k1);
for(int i=0;i<k1;i++){
scanf("%d%lf",&p[i].k,&p[i].c);
}
scanf("%d",&k2);
for(int i=0;i<k2;i++){
int exp;
double c1;
scanf("%d%lf",&exp,&c1);
for(int j=0;j<k1;j++){
flag[p[j].k+exp]+=(c1*p[j].c);
}
}
for(int i=0;i<2001;i++){
if(flag[i]!=0.0)
temp++;
}
printf("%d",temp);
for(int i=2000;i>=0;i--){
if(flag[i]!=0.0){
printf(" %d %.1f",i,flag[i]);
}
}
return 0;
}
二分查找——难题(P169)
#include <iostream>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
// 将n由radix进制转化为10进制
long long convert(string n, long long radix){
long long base = 1;
long long num = 0;
for(auto lt = n.rbegin(); lt != n.rend(); lt++){
int temp = isdigit(*lt) ? *lt - '0' : *lt - 'a' + 10;
num += temp * base;
base *= radix;
}
return num;
}
int main(int argc, const char * argv[]) {
string n1, n2, t;
int tag;
long long radix;
cin >> n1 >> n2 >> tag >> radix;
if(tag == 2){
t = n1;
n1 = n2;
n2 = t;
}
long long num = convert(n1, radix);
char lt = *max_element(n2.begin(), n2.end());
long long low = (isdigit(lt) ? lt - '0' : lt - 'a' + 10) + 1;
long long high = max(low, num) + 1;
long long mid;
// 记录是否找到答案
bool flag = false;
// 二分查找
while (low <= high) {
mid = (low + high) / 2;
long long res = convert(n2, mid);
// 数据有可能溢出,溢出的情况下res < 0
if(res < 0 || res > num){
high = mid - 1;
}else if(res < num){
low = mid + 1;
}else{
low = mid;
flag = true;
break;
}
}
if(flag){
printf("%lld", low);
}else{
printf("Impossible");
}
return 0;
}
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int flag=0,f[3];
char a[4]={'W','T','L'};
double sum,k[3],m[3];
for(int i=0;i<3;i++){
cin>>k[0]>>k[1]>>k[2];
double max=k[0];
for(int j=0;j<3;j++){
if(k[j]>max){
max=k[j];
flag=j;
}
}
m[i]=max;
f[i]=flag;
}
sum=(m[0]*m[1]*m[2]*0.65-1)*2.0;
for(int i=0;i<3;i++){
cout<<a[f[i]]<<" ";
}
printf("%.2f\n",sum);
return 0;
}
#include<stdio.h>
struct STU{
int ID;
int grade[4];//A,C,M,E;
int vivid;
}stu[1000010];
char CH[6]="ACME";
int rank[4][110];//排名
int num[4][110];//人数分段 ACME
void Init(){
int i,j;
for(i=0;i<4;i++){
for(j=0;j<110;j++){
rank[i][j]=0;
num[i][j]=0;
}
}
return;
}
void GetGrade(int n){
int i,temp,A,C,M,E;
for(i=0;i<n;i++){
scanf("%d",&temp);
stu[temp].vivid=1;//学号有效
scanf("%d%d%d",&C,&M,&E);
num[1][C]++;
num[2][M]++;
num[3][E]++;
A=( C + M + E +1)/3;
num[0][A]++;
stu[temp].grade[0]=A;
stu[temp].grade[1]=C;
stu[temp].grade[2]=M;
stu[temp].grade[3]=E;
}
return;
}
void DataOp(){
int i,j;
for(i=0;i<4;i++){
for(j=100;j>=0;j--){
num[i][j]+=num[i][j+1];
rank[i][j]=num[i][j+1]+1;
}
}
return;
}
void print(int ID){
int i,imax,grade,mgrade;
if(stu[ID].vivid==0){
printf("N/A\n");
}else{
mgrade=stu[ID].grade[0];
imax=0;
for(i=1;i<4;i++){
if(rank[i][stu[ID].grade[i]]<rank[imax][mgrade]){
imax=i;
mgrade=stu[ID].grade[i];
}
}
printf("%d %c\n",rank[imax][mgrade],CH[imax]);
}
return;
}
int main(){
int N,M,id;
int i;
scanf("%d%d",&N,&M);
Init();
GetGrade(N);
DataOp();
for(i=0;i<M;i++){
scanf("%d",&id);
print(id);
}
return 0;
}
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
const int maxv=1010;
const int INF=1000000000;
vector<int> G[maxv];
int current;
bool vis[maxv]={false};
void DFS(int u){
if(u==current)
return;
vis[u]=true;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vis[v]==false){
DFS(v);
}
}
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=0;i<k;i++){
scanf("%d",¤t);
memset(vis,false,sizeof(vis));
int count=0; //连通块个数
for(int j=1;j<=n;j++){
if(j!=current&&vis[j]==false){
DFS(j);
count++;
}
}
if(n==1) //注意特殊情况(只有一个城市)
printf("%d\n",count);
else
printf("%d\n",count-1);
}
return 0;
}
#include <stdio.h>
bool isPrime(int n){ //判断是否为素数
if(n<=1)
return false;
for(int i=2;i*i<=n;i++){
if(n%i==0)
return false;
}
return true;
}
int reverse(int n,int d){ //十进制转换为d进制,并逆置
int ans[40],num=0,sum=0,count=1;
do{
ans[num++]=n%d;
n=n/d;
}while(n!=0);
for(int i=num-1;i>=0;i--){
sum+=ans[i]*count;
count*=d;
}
return sum;
}
int main(){
int a,b;
while(scanf("%d",&a)!=EOF){
if(a<0)
break;
scanf("%d",&b);
int rev=reverse(a,b);
if(isPrime(a)&&isPrime(rev)){
printf("Yes\n");
}else
printf("No\n");
}
return 0;
}
#include <stdio.h>
int main() {
int n,b,ans[40],num=0;
bool flag=true;
scanf("%d%d",&n,&b);
do{
ans[num++]=n%b;
n/=b;
}while(n!=0);
for(int i=0;i<num/2;i++){
if(ans[i]!=ans[num-i-1])
flag=false;
}
if(flag==true)
printf("Yes\n");
else
printf("No\n");
for(int i=num-1;i>0;i--){
printf("%d ",ans[i]);
}
printf("%d\n",ans[0]);
return 0;
}
#include <stdio.h>
#include <queue>
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
int n,post[35],in[35];
node* create(int postL,int postR,int inL,int inR){ //后序和中序构造二叉树
if(postL>postR){
return NULL;
}
node* root=new node;
root->data=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR])
break;
}
int numleft=k-inL;
root->lchild=create(postL,postL+numleft-1,inL,k-1);
root->rchild=create(postL+numleft,postR-1,k+1,inR);
return root;
}
int num=0;
void LayerOrder(node* root){ //层序遍历
queue<node*> q;
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
printf("%d",now->data);
num++;
if(num<n)
printf(" ");
if(now->lchild!=NULL){
q.push(now->lchild);
}
if(now->rchild!=NULL){
q.push(now->rchild);
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
node* root=create(0,n-1,0,n-1);
LayerOrder(root);
printf("\n");
return 0;
}
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxv=10010;
vector<int> G[maxv],ans;
int temp,block,deepest=0;
int n;
bool vis[maxv]={false};
void DFS(int u,int h){
vis[u]=true;
if(h>temp) temp=h;
for(int i=0;i<G[u].size();i++){
if(vis[G[u][i]]==false)
DFS(G[u][i],h+1);
}
}
void DFSTrave(int root){
DFS(root,1);
block++;
for(int u=1;u<=n;u++){
if(vis[u]==false){
DFS(u,1);
block++;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=n;i++){
temp=block=0;
fill(vis,vis+maxv,false);
DFSTrave(i);
if(block==1){ //n个点n-1条边的连通图必为树
if(temp==deepest) ans.push_back(i); //本次遍历得到的树深度与最大深度相同
else if(temp>deepest){
deepest=temp;
ans.clear();
ans.push_back(i);
}
}
else{ //若图不连通
printf("Error: %d components\n",block);
break;
}
}
if(ans.size()!=0){
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf("%d\n",ans[i]);
}
return 0;
}
方法一:用long long实现(满分20分拿11分)
#include <stdio.h>
int main(){
int flag1[10]={0},flag2[10]={0};
bool flag=true;
long long a,b,tmp;
scanf("%lld",&a);
tmp=b=2*a;
while(a!=0){
int x=a%10;
flag1[x]++;
a/=10;
}
while(b!=0){
int x=b%10;
flag2[x]++;
b/=10;
}
for(int i=0;i<10;i++){
if(flag1[i]!=flag2[i]){
flag=false;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
printf("%lld\n",tmp);
return 0;
}
方法二:记录进位
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main(){
int flag1[10]={0},flag2[10]={0},tmp[25],num[25];
bool flag=true;
string a;
getline(cin,a);
int len=a.size();
for(int i=0;i<len;i++){
tmp[i]=a[i]-'0';
flag1[tmp[i]]++;
}
int carry=0;
for(int i=0;i<len;i++){
num[i]=(tmp[len-i-1]*2+carry)%10;
carry=(tmp[len-i-1]*2+carry)/10;
flag2[num[i]]++;
}
if(carry==1){
num[len]=1;
flag2[1]++;
}
for(int i=0;i<10;i++){
if(flag1[i]!=flag2[i])
flag=false;
}
if(flag){
printf("Yes\n");
}else
printf("No\n");
if(num[len]==1)
printf("1");
for(int i=len-1;i>=0;i--){
printf("%d",num[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Student{
char id[13];
int score;
int location;
int krank;
}s[1000010];
bool cmp(Student a,Student b){
if(a.score!=b.score)
return a.score>b.score;
else
return strcmp(a.id,b.id)<0;
}
int main(){
int k,num=0;
scanf("%d",&k);
for(int i=1;i<=k;i++){
int count;
scanf("%d",&count);
for(int j=0;j<count;j++){
scanf("%s %d",s[num].id,&s[num].score);
s[num].location=i;
num++;
}
sort(s+num-count,s+num,cmp);
s[num-count].krank=1;
for(int j=num-count+1;j<num;j++){
if(s[j].score==s[j-1].score){
s[j].krank=s[j-1].krank;
}else{
s[j].krank=j+1-(num-count);
}
}
}
printf("%d\n",num);
int r=1;
sort(s,s+num,cmp);
for(int i=0;i<num;i++){
if(i>0&&s[i].score!=s[i-1].score)
r=i+1;
printf("%s ",s[i].id);
printf("%d %d %d\n",r,s[i].location,s[i].krank);
}
return 0;
}
#include <stdio.h>;
int main() {
int a,b,c,a1[2]={0},b1[2]={0},c1[2]={0};
char k[13]={'0','1','2','3','4','5','6','7','8','9','A','B','C'};
scanf("%d%d%d",&a,&b,&c);
a1[0]=a/13;
a1[1]=a%13;
b1[0]=b/13;
b1[1]=b%13;
c1[0]=c/13;
c1[1]=c%13;
printf("#%c%c%c%c%c%c\n",k[a1[0]],k[a1[1]],k[b1[0]],k[b1[1]],k[c1[0]],k[c1[1]]);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Student{
char name[15],id[15];
int grade;
}s[100010];
bool cmp1(Student a,Student b){
return strcmp(a.id,b.id)<0;
}
bool cmp2(Student a,Student b){
if(strcmp(a.name,b.name)!=0)
return strcmp(a.name,b.name)<0;
else
return strcmp(a.id,b.id)<0;
}
bool cmp3(Student a,Student b){
if(a.grade!=b.grade)
return a.grade<b.grade;
else
return strcmp(a.id,b.id)<0;
}
int main(){
int n,c;
scanf("%d%d",&n,&c);
for(int i=0;i<n;i++){
scanf("%s %s %d",s[i].id,s[i].name,&s[i].grade);
}
if(c==1)
sort(s,s+n,cmp1);
else if(c==2)
sort(s,s+n,cmp2);
else
sort(s,s+n,cmp3);
for(int i=0;i<n;i++){
printf("%s %s %d\n",s[i].id,s[i].name,s[i].grade);
}
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxv=505;
const int INF=1000000000;
int pre[maxv],d[maxv],c[maxv];
int n,m,st,ed,G[maxv][maxv],cost[maxv][maxv];
bool vis[maxv]={false};
void Dijkstra(int s){
fill(d,d+maxv,INF);
fill(c,c+maxv,INF);
d[s]=0;
c[s]=0;
for(int i=0;i<n;i++){
int u=-1,min=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&d[j]<min){
u=j;
min=d[j];
}
}
if(u==-1)
return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
c[v]=c[u]+cost[u][v];
pre[v]=u;
}else if(d[u]+G[u][v]==d[v]){
if(c[u]+cost[u][v]<c[v]){
c[v]=c[u]+cost[u][v];
pre[v]=u;
}
}
}
}
}
}
void DFS(int v){
if(v==st){
printf("%d ",v);
return;
}
DFS(pre[v]);
printf("%d ",v);
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);
int u,v;
fill(G[0],G[0]+maxv*maxv,INF);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
scanf("%d%d",&G[u][v],&cost[u][v]);
G[v][u]=G[u][v];
cost[v][u]=cost[u][v];
}
Dijkstra(st);
DFS(ed);
printf("%d %d\n",d[ed],c[ed]);
return 0;
}
#include <stdio.h>;
#include <string.h>
int main() {
char str[100];
gets(str);
int len=strlen(str);
int n1=(len+2)/3,n3=n1,n2=len-n1-n3+2;
for(int i=0;i<n1-1;i++){
printf("%c",str[i]);
for(int j=0;j<n2-2;j++){
printf(" ");
}
printf("%c\n",str[len-1-i]);
}
for(int i=n1-1;i<n1+n2-1;i++){
printf("%c",str[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
const int maxn=100005;
struct Node{
int flag; //用来标记是否在第一个链表中出现
char data;
int next;
}node[maxn];
int main() {
int n,s1,s2,address,next;
char data;
for(int i=0;i<maxn;i++){
node[i].flag=0;
}
scanf("%d%d%d",&s1,&s2,&n);
for(int i=0;i<n;i++){ //串联链表
scanf("%d %c %d",&address,&data,&next);
node[address].data=data;
node[address].next=next;
}
int p;
for(p=s1;p!=-1;p=node[p].next){
node[p].flag=1;
}
for(p=s2;p!=-1;p=node[p].next){
if(node[p].flag==1)
break;
}
if(p!=-1){
printf("%05d\n",p);
}else{
printf("-1\n");
}
return 0;
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int maxn=2005;
int n,k;
int weight[maxn]={0},G[maxn][maxn]={0},sum=0;
bool vis[maxn]={false};
map<string,int> stringToInt;
map<int,string> intToString;
map<string,int> Gang;
int change(string s){ //转换函数
if(stringToInt.find(s)!=stringToInt.end())
return stringToInt[s];
else{
stringToInt[s]=sum;
intToString[sum]=s;
return sum++;
}
}
void DFS(int u,int &head,int &num,int &total){
num++;
vis[u]=true;
if(weight[u]>weight[head]){
head=u;
}
for(int i=0;i<sum;i++){
if(G[u][i]>0){
total+=G[u][i];
G[u][i]=G[i][u]=0;
if(vis[i]==false){
DFS(i,head,num,total);
}
}
}
}
void DFSTrave(){
for(int i=0;i<sum;i++){
if(vis[i]==false){
int head=i,num=0,total=0;
DFS(i,head,num,total);
if(num>2&&total>k){
Gang[intToString[head]]=num;
}
}
}
}
int main(){
cin>>n>>k;
string a,b;
int w;
for(int i=0;i<n;i++){
cin>>a>>b>>w;
int id1=change(a);
int id2=change(b);
weight[id1]+=w;
weight[id2]+=w;
G[id1][id2]+=w;
G[id2][id1]+=w;
}
DFSTrave();
cout<<Gang.size()<<endl;
map<string,int>::iterator it;
for(it=Gang.begin();it!=Gang.end();it++){
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
#include <stdio.h>
struct Person{
char name[15],psd[15];
}p[1010];
int main() {
int n,count=0,num=0;
Person flag[1010];
scanf("%d",&n);
for(int i=0;i<n;i++){
bool tmp=false;
scanf("%s %s",&p[i].name,&p[i].psd);
for(int j=0;j<10;j++){
if(p[i].psd[j]=='1'){
p[i].psd[j]='@';
tmp=true;
}else if(p[i].psd[j]=='0'){
p[i].psd[j]='%';
tmp=true;
}else if(p[i].psd[j]=='l'){
p[i].psd[j]='L';
tmp=true;
}else if(p[i].psd[j]=='O'){
p[i].psd[j]='o';
tmp=true;
}
}
if(tmp==true){
count++;
flag[num++]=p[i];
}
}
if(count>0){
printf("%d\n",count);
for(int i=0;i<count;i++){
printf("%s %s\n",flag[i].name,flag[i].psd);
}
}else{
if(n==1)
printf("There is %d account and no account is modified\n",n);
else
printf("There are %d accounts and no account is modified\n",n);
}
return 0;
}
#include <stdio.h>
struct Student{
char name[15],id[15];
char sex;
int grade;
}s,smax,smin;
int main() {
int n,count=0;
smax.grade=-1;
smin.grade=101,
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s %c %s %d",s.name,&s.sex,s.id,&s.grade);
if(s.sex=='F'&&s.grade>smax.grade){
smax=s;
}else if(s.sex=='M'&&s.grade<smin.grade){
smin=s;
}
}
if(smax.grade>=0){
printf("%s %s\n",smax.name,smax.id);
count++;
}
else
printf("Absent\n");
if(smin.grade<=100){
printf("%s %s\n",smin.name,smin.id);
count++;
}
else
printf("Absent\n");
if(count==2)
printf("%d\n",smax.grade-smin.grade);
else
printf("NA\n");
return 0;
}
#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=26*26*26*10+1;
vector<int> v[maxn];
int getid(char a[]){
int sum=0;
for(int i=0;i<3;i++){
sum=sum*26+(a[i]-'A');
}
sum=sum*10+(a[3]-'0');
return sum;
}
int main(){
int n,k,tmp;
char name[5];
scanf("%d%d",&n,&k);
for(int i=0;i<k;i++){
int id,num;
scanf("%d%d",&id,&num);
for(int j=0;j<num;j++){
scanf("%s",name);
tmp=getid(name);
v[tmp].push_back(id);
}
}
for(int i=0;i<n;i++){
scanf("%s",name);
int nid=getid(name);
sort(v[nid].begin(),v[nid].end());
printf("%s %d",name,v[nid].size());
for(int j=0;j<v[nid].size();j++){
printf(" %d",v[nid][j]);
}
printf("\n");
}
return 0;
}
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
const int maxn=1010;
string s;
int dp[maxn][maxn];
int main(){
getline(cin,s);
int len=s.size(),ans=1;
memset(dp,0,sizeof(dp));
//边界
for(int i=0;i<len;i++){
dp[i][i]=1;
if(i<len-1){
if(s[i]==s[i+1]){
dp[i][i+1]=1;
ans=2;
}
}
}
//状态转移方程
for(int L=3;L<=len;L++){
for(int i=0;i<len&&i+L-1<len;i++){
int j=i+L-1;
if(s[i]==s[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
ans=L;
}
}
}
printf("%d\n",ans);
return 0;
}
#include <string>
#include <iostream>
using namespace std;
const int maxn=100010;
int main(){
int n,a[maxn],count=0;
cin>>n;
int temp[maxn]={0};
for(int i=0;i<n;i++){
cin>>a[i];
temp[a[i]]++;
}
for(int i=0;i<n;i++){
if(temp[a[i]]==1){
cout<<a[i];
break;
}
count++;
}
if(count==n)
cout<<"None";
cout<<endl;
return 0;
}
#include <stdio.h>
int main() {
int k;
char s[5]={'S','H','C','D','J'};
int start[55],end[55],next[55];
scanf("%d",&k);
for(int i=1;i<=54;i++){
start[i]=i;
}
for(int i=1;i<=54;i++){
scanf("%d",&next[i]);
}
for(int i=0;i<k;i++){
for(int j=1;j<=54;j++){
end[next[j]]=start[j];
}
for(int j=1;j<=54;j++){
start[j]=end[j];
}
}
for(int i=1;i<54;i++){
int temp1=(end[i]-1)/13;
int temp2=(end[i]-1)%13+1;
printf("%c%d ",s[temp1],temp2);
}
printf("%c%d\n",s[(end[54]-1)/13],(end[54]-1)%13+1);
return 0;
}
#include <stdio.h>
#include <vector>
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
vector<int> origin,pre,post,preM,postM;
void insert(node* &root,int data){ //BST的插入操作
if(root==NULL){
root=new node;
root->data=data;
root->lchild=root->rchild=NULL;
return;
}
if(data<root->data)
insert(root->lchild,data);
else
insert(root->rchild,data);
}
void preOrder(node* root,vector<int>&vi){ //先序遍历
if(root==NULL)
return;
vi.push_back(root->data);
preOrder(root->lchild,vi);
preOrder(root->rchild,vi);
}
void preOrderMirror(node* root,vector<int>&vi){ //镜像数先序遍历
if(root==NULL)
return;
vi.push_back(root->data);
preOrderMirror(root->rchild,vi);
preOrderMirror(root->lchild,vi);
}
void postOrder(node* root,vector<int>&vi){ //后序遍历
if(root==NULL)
return;
postOrder(root->lchild,vi);
postOrder(root->rchild,vi);
vi.push_back(root->data);
}
void postOrderMirror(node* root,vector<int>&vi){ //镜像树后序遍历
if(root==NULL)
return;
postOrderMirror(root->rchild,vi);
postOrderMirror(root->lchild,vi);
vi.push_back(root->data);
}
int main(){
int n,x;
node* root=NULL;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
origin.push_back(x);
insert(root,x);
}
preOrder(root,pre);
preOrderMirror(root,preM);
postOrder(root,post);
postOrderMirror(root,postM);
if(pre==origin){
printf("YES\n");
for(int i=0;i<post.size();i++){
printf("%d",post[i]);
if(i<post.size()-1)
printf(" ");
}
}else if(preM==origin){
printf("YES\n");
for(int i=0;i<postM.size();i++){
printf("%d",postM[i]);
if(i<postM.size()-1)
printf(" ");
}
}else{
printf("NO\n");
}
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=100010;
const int INF=1000000000;
int sum[maxn]={0};
int upper(int left,int right,int x){ //二分查找关键代码
while(left<right){
int mid=(left+right)/2;
if(sum[mid]<x){
left=mid+1;
}else{
right=mid;
}
}
return left;
}
int main(){
int n,m,num=INF;
scanf("%d%d",&n,&m);
sum[0]=0;
for(int i=1;i<=n;i++){ //求sum数组
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
for(int i=1;i<=n;i++){
int j=upper(i,n+1,sum[i-1]+m);
if(sum[j-1]-sum[i-1]==m){
num=m;
break;
}else if(sum[j-1]-sum[i-1]<m&&j<=n){
num=min(num,sum[j]-sum[i-1]);
}
}
for(int i=1;i<=n;i++){
int j=upper(i,n+1,sum[i-1]+num);
if(sum[j]-sum[i-1]==num)
printf("%d-%d\n",i,j);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxc=210;
const int maxn=10010;
int a[maxn],dp[maxn];
int flag[maxc];
int main(){
int n,m,x,l,len=0;
scanf("%d%d",&n,&m);
memset(flag,-1,sizeof(flag)); //将整个标记数组置为-1
for(int i=0;i<m;i++){
scanf("%d",&x);
flag[x]=i; //设置标记数组前m个数
}
scanf("%d",&l);
for(int i=0;i<l;i++){
scanf("%d",&x);
if(flag[x]>=0){
a[len++]=flag[x];
}
}
int ans=-1;
for(int i=0;i<len;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[j]<=a[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}
#include <stdio.h>;
#include <algorithm>
using namespace std;
int main() {
int n,m,left,right,a[100010],dis[100010]={0},sum=0; //dis数组表示v1顺时针到任意结点的距离
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
if(i>1){
dis[i]=dis[i-1]+a[i-1];
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&left,&right);
if(right<left) //注意若left大于right,则交换其位置
swap(left,right);
int d1=dis[right]-dis[left];
int d2=sum-d1;
printf("%d\n",d1>d2?d2:d1);
}
return 0;
}
方法一:使用string(满分25分拿21分,数据量大容易超时)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> v[2505];
int main(){
int n,k;
string name;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
int id,num;
cin>>name>>num;
for(int j=0;j<num;j++){
scanf("%d",&id);
v[id].push_back(name);
}
}
for(int i=1;i<=k;i++){
printf("%d %d\n",i,v[i].size());
sort(v[i].begin(),v[i].end());
for(int j=0;j<v[i].size();j++){
cout<<v[i][j]<<endl;
}
}
return 0;
}
方法二:使用char数组(拿满分25分)
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
vector<int> v[2505];
char name[40005][5];
bool cmp(int a,int b){
return strcmp(name[a],name[b])<0;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
int id,num;
scanf("%s %d",name[i],&num);
for(int j=0;j<num;j++){
scanf("%d",&id);
v[id].push_back(i);
}
}
for(int i=1;i<=k;i++){
printf("%d %d\n",i,v[i].size());
sort(v[i].begin(),v[i].end(),cmp);
for(int j=0;j<v[i].size();j++){
printf("%s\n",name[v[i][j]]);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
int main(){
int n,m,a[maxn],tmp[505]={0};
cin>>n;
cin>>m;
int temp[maxn]={0};
for(int i=0;i<n;i++){
cin>>a[i];
tmp[a[i]]++;
}
sort(a,a+n);
int i,j;
for(i=0;i<505;i++){
for(j=0;j<505;j++){
if(tmp[i]>1&&tmp[j]>1){
if(i+j==m){
cout<<i<<" "<<j<<endl;
return 0;
}
}else if(tmp[i]==1&&tmp[j]==1){
if(i+j==m&&i!=j){
cout<<i<<" "<<j<<endl;
return 0;
}
}
}
}
if(i>500&&j>500){
cout<<"No Solution"<<endl;
}
return 0;
}
#include <iostream>
using namespace std;
int main(){
int n,num=0,a=1,left,now,right;
cin>>n;
while(n/a!=0){
left=n/(a*10);
now=n/a%10;
right=n%a;
if(now==0)
num+=left*a;
else if(now==1)
num+=left*a+right+1;
else
num+=(left+1)*a;
a*=10;
}
cout<<num<<endl;
return 0;
}
#include <string>
#include <iostream>
using namespace std;
int main(){
bool temp[128]={false};
string str1,str2;
getline(cin,str1);
getline(cin,str2);
for(int i=0;i<str2.size();i++){
temp[str2[i]]=true;
}
for(int i=0;i<str1.size();i++){
if(!temp[str1[i]])
cout<<str1[i];
}
cout<<endl;
return 0;
}
#include <stdio.h>
#include <stack>
using namespace std;
int main(){
stack<int> s;
int m,n,k,a[1005];
scanf("%d%d%d",&m,&n,&k);
while(k--){
while(!s.empty()){
s.pop();
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int num=1;
bool flag=true;
for(int i=1;i<=n;i++){
s.push(i);
if(s.size()>m){
flag=false;
break;
}
while(!s.empty()&&s.top()==a[num]){
s.pop();
num++;
}
}
if(s.empty()==true&&flag==true)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=100005;
struct Node{
int address;
int key;
int next;
bool order; //结点是否在链表上
}node[maxn];
int cmp(Node a,Node b){
if(a.order==false||b.order==false)
return a.order>b.order;
else
return a.key<b.key;
}
int main(){
int n,s,key,address,next;
for(int i=0;i<maxn;i++){
node[i].order=false;
}
scanf("%d%d",&n,&s);
for(int i=0;i<n;i++){ //串联链表
scanf("%d",&address);
scanf("%d%d",&node[address].key,&node[address].next);
node[address].address=address;
}
int p=s,count=0;
while(p!=-1){ //遍历链表,并记录有效结点个数
node[p].order=true;
count++;
p=node[p].next;
}
if(count==0){
printf("0 -1\n");
}
else{
sort(node,node+maxn,cmp);
n=count; //有效结点
printf("%d %05d\n",count,node[0].address);
for(int i=0;i<count-1;i++){
printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address);
}
printf("%05d %d -1\n",node[count-1].address,node[count-1].key);
}
return 0;
}
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int weight;
vector<int> child;
}Node[110];
bool cmp(int a,int b){
return Node[a].weight>Node[b].weight;
}
int n,m,s;
int path[105];
void DFS(int index,int num,int sum){
if(sum>s)
return;
if(sum==s){
if(Node[index].child.size()!=0)
return;
for(int i=0;i<num;i++){
printf("%d",Node[path[i]].weight);
if(i<num-1)
printf(" ");
else
printf("\n");
}
return;
}
for(int i=0;i<Node[index].child.size();i++){
int child=Node[index].child[i];
path[num]=child;
DFS(child,num+1,sum+Node[child].weight);
}
}
int main(){
int parent,k,child;
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n;i++){
scanf("%d",&Node[i].weight);
}
for(int i=0;i<m;i++){
scanf("%d%d",&parent,&k);
for(int j=0;j<k;j++){
scanf("%d",&child);
Node[parent].child.push_back(child);
}
sort(Node[parent].child.begin(),Node[parent].child.end(),cmp);
}
path[0]=0;
DFS(0,1,Node[0].weight);
return 0;
}
#include <stdio.h>
#include <map>
using namespace std;
int main() {
int m,n,x;
map<int,int> mp;
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&x);
if(mp.find(x)!=mp.end())
mp[x]++;
else
mp[x]=1;
}
}
int k,max=0;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
if(it->second>max){
max=it->second;
k=it->first;
}
}
printf("%d\n",k);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Person{
char name[15];
int age,wealth;
}p[100010];
bool cmp(Person a,Person b){
if(a.wealth!=b.wealth)
return a.wealth>b.wealth;
else if(a.age!=b.age)
return a.age<b.age;
return strcmp(a.name,b.name)<0;
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++){
scanf("%s %d %d",p[i].name,&p[i].age,&p[i].wealth);
}
sort(p,p+n,cmp);
for(int i=0;i<k;i++){
int m,left,right;
scanf("%d %d %d",&m,&left,&right);
printf("Case #%d:\n",i+1);
int count=0,j=0;
for(int j=0;j<n&&count<m;j++){
if(p[j].age>=left&&p[j].age<=right){
printf("%s %d %d\n",p[j].name,p[j].age,p[j].wealth);
count++;
}
}
if(count==0)
printf("None\n");
}
return 0;
}
法一:使用carry进位
#include <stdio.h>;
int main() {
int g1,s1,k1,g2,s2,k2,g,s,k,carry=0;
scanf("%d.%d.%d %d.%d.%d",&g1,&s1,&k1,&g2,&s2,&k2);
k=(k1+k2)%29;
carry=(k1+k2)/29;
s=(s1+s2+carry)%17;
carry=(s1+s2+carry)/17;
g=g1+g2+carry;
printf("%d.%d.%d\n",g,s,k);
return 0;
}
法二:先转换成最小单位,最后转换成对应货币
#include <stdio.h>;
long long change(long long a,int b,int c){ //a可能溢出,使用long long
long long sum;
sum=a*493+b*29+c;
return sum;
}
int main() {
int s1,k1,s2,k2,g,s,k;
long long res,g1,g2;
scanf("%lld.%d.%d %lld.%d.%d",&g1,&s1,&k1,&g2,&s2,&k2);
res=change(g1+g2,s1+s2,k1+k2);
g=res/493;
s=res/29%17;
k=res%29;
printf("%d.%d.%d\n",g,s,k);
return 0;
}
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main(){
char str[7][4]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
int tmp1,tmp2,tmp3,num;
string a,b,c,d;
getline(cin,a);
getline(cin,b);
for(int i=0;i<a.size()&&i<b.size();i++){
if(a[i]==b[i]){
if(a[i]>='A'&&a[i]<='G'){
tmp1=a[i]-'A';
num=i;
break;
}
}
}
for(int i=num+1;i<a.size()&&i<b.size();i++){
if(a[i]==b[i]){
if(a[i]>='0'&&a[i]<='9'){
tmp2=a[i]-'0';
break;
}else if(a[i]>='A'&&a[i]<='N'){
tmp2=a[i]-'A'+10;
break;
}
}
}
getline(cin,c);
getline(cin,d);
for(int i=0;i<c.size()&&i<d.size();i++){
if(c[i]==d[i]){
if(c[i]>='A'&&c[i]<='Z'){
tmp3=i;
break;
}else if(c[i]>='a'&&c[i]<='z'){
tmp3=i;
break;
}
}
}
printf("%s %02d:%02d\n",str[tmp1],tmp2,tmp3);
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,CBT[1010],num[1010],index=0;
void inOrder(int root){
if(root>n)
return;
inOrder(2*root);
CBT[root]=num[index++];
inOrder(2*root+1);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&num[i]);
}
sort(num,num+n);
inOrder(1);
for(int i=1;i<=n;i++){
printf("%d",CBT[i]);
if(i<n)
printf(" ");
}
printf("\n");
return 0;
}
#include <stdio.h>
int main() {
int n;
long long a,b,c;
bool flag=false;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld %lld",&a,&b,&c);
long long res=a+b;
if(a>0&&b>0&&res<0)
flag=true;
else if(a<0&&b<0&&res>=0)
flag=false;
else if(a+b>c)
flag=true;
else
flag=false;
if(flag==true)
printf("Case #%d: true\n",i);
else
printf("Case #%d: false\n",i);
}
return 0;
}
法一:直接求中位数(满分25分得17分)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
vector<int> v;
scanf("%d",&n);
v.resize(n);
for(int i=0;i<v.size();i++){
scanf("%d",&v[i]);
}
sort(v.begin(),v.end());
printf("%d\n",v[n/2]);
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
bool check(char c){
if(c>='0'&&c<='9')
return true;
if(c>='a'&&c<='z')
return true;
if(c>='A'&&c<='Z')
return true;
return false;
}
int main(){
map<string,int> mp; //单词->数字
string s;
getline(cin,s);
int i=0;
while(i<s.length()){
string word;
while(i<s.length()&&check(s[i])==true){
if(s[i]>='A'&&s[i]<='Z'){
s[i]+=32;
}
word+=s[i];
i++;
}
if(word!=""){
if(mp.find(word)==mp.end()){
mp[word]=1;
}else{
mp[word]++;
}
}
while(i<s.length()&&check(s[i])==false){
i++;
}
}
string ans;
int max=0;
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
if(it->second>max){
ans=it->first;
max=it->second;
}
}
cout<<ans<<" "<<max<<endl;
return 0;
}
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxv=1010;
struct Node{
int v; //顶点编号
int layer; //层数
};
vector<Node> adj[maxv];
int n,l;
bool inq[maxv]={false};
int BFS(int s,int l){
int numForward=0;
queue<Node> q;
Node start;
start.v=s;
start.layer=0;
q.push(start);
inq[start.v]=true;
while(!q.empty()){
Node topNode=q.front();
q.pop();
int u=topNode.v;
for(int i=0;i<adj[u].size();i++){
Node next=adj[u][i];
next.layer=topNode.layer+1;
if(inq[next.v]==false&&next.layer<=l){
q.push(next);
inq[next.v]=true;
numForward++;
}
}
}
return numForward;
}
int main(){
Node user;
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++){
int num,x;
user.v=i;
scanf("%d",&num);
for(int j=0;j<num;j++){
scanf("%d",&x);
adj[x].push_back(user);
}
}
int k;
scanf("%d",&k);
while(k--){
int query;
memset(inq,false,sizeof(inq)); //每次查询都先初始化判断数组
scanf("%d",&query);
int numForward=BFS(query,l);
printf("%d\n",numForward);
}
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
scanf("%d",&n);
getchar();
string s,ans;
getline(cin,s);
for(int i=1;i<n;i++){
getline(cin,ans);
int j=0;
for(j=0;j<s.size()&&j<ans.size();j++){
if(s[s.size()-1-j]!=ans[ans.size()-1-j]){
break;
}
}
if(j==0){
s="nai";
break;
}
s=s.substr(s.size()-j);
}
cout<<s<<endl;
return 0;
}
#include <iostream>
using namespace std;
bool isprime(int n){ //判断是否为素数
if(n<=1)
return false;
for(int i=2;i*i<=n;i++){
if(n%i==0)
return false;
}
return true;
}
int main(){
int n,tsize,temp,s[10010]={0};
cin>>tsize>>n;
while(!isprime(tsize)) //找到最近的素数作为哈希表长度
tsize++;
for(int i=0;i<n;i++){
cin>>temp;
int j,k;
for(j=0;j<tsize;j++){
k=(temp+j*j)%tsize; //平方探测法
if(!s[k]){
s[k]=1;
cout<<k;
break;
}
}
if(j==tsize) cout<<"-"; //没有找到插入位置
if(i!=n-1) cout<<" ";
}
cout<<endl;;
return 0;
}
(难题P84)
关键难点在处理零上,笨方法可以拿16分(满分25分)
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int len,k=0,num=0;
char a[15],s[30][5],c[10][5]={"Shi","Bai","Qian","Wan","Yi"};
char b[15][5]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
cin>>a;len=strlen(a);
if(a[0]=='-'){ //先输出负数符号
cout<<"Fu ";
k++;
}
if(len==1&&a[0]=='0') cout<<b[0]; //特例,只有一位数且为0时,直接输出"ling"
bool flag=false;
for(int i=k;i<len;i++){
if(a[i]=='0'&&len-i-1!=4) flag=true; //当前位为0且不是个位,低一位不为0且不为千位(千位的高一位为0时不用读零,如808000),输出“ling”
if(a[i]!='0'){
if(flag==true){ //没有i+1<len 这个条件的话输入10会输出"yi Shi ling"
strcpy(s[num++],b[0]);
flag=false;
}
strcpy(s[num++],b[a[i]-'0']); //当前位不为0时
if((len-i)%4==2) strcpy(s[num++],c[0]); //十,输出"Shi"
if((len-i)%4==3) strcpy(s[num++],c[1]); //百,输出"Bai"
if((len-i)%4==0) strcpy(s[num++],c[2]); //千,输出"Qian"
}
if(len-i==5){
if(a[i]=='0'&&a[i-1]=='0'&&a[i-2]=='0'&&a[i-3]=='0'); //万,输出"Wan"(没有出现万这个小节位数全为0时,如800000008)
else strcpy(s[num++],c[3]);
}
if(len-i==9) strcpy(s[num++],c[4]); //亿,输出"Yi"
}
for(int i=0;i<num;i++){
cout<<s[i];
if(i!=num-1)
cout<<" ";
}
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Student{
char name[15],id[15];
int grade;
}s[10010];
bool cmp(Student a,Student b){
return a.grade>b.grade;
}
int main(){
int n,left,right,count=0;
scanf("%d",&n);
int i;
for(i=0;i<n;i++){
scanf("%s %s %d",s[i].name,s[i].id,&s[i].grade);
}
sort(s,s+n,cmp);
scanf("%d%d",&left,&right);
for(int i=0;i<n;i++){
if(s[i].grade>=left&&s[i].grade<=right){
printf("%s %s\n",s[i].name,s[i].id);
count++;
}
}
if(count==0){
printf("NONE\n");
}
return 0;
}
#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
int n,pre[35],in[35],num=0,num1=0,num2=0;
node* create(int preL,int preR,int inL,int inR){ //先序和中序构造二叉树
if(preL>preR){
return NULL;
}
node* root=new node;
root->data=pre[preL];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==pre[preL])
break;
}
int numleft=k-inL;
root->lchild=create(preL+1,preL+numleft,inL,k-1);
root->rchild=create(preL+numleft+1,preR,k+1,inR);
return root;
}
void postOrder(node* root){
if(root==NULL){
return;
}
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d",root->data);
num++;
if(num<n){
printf(" ");
}
}
int main(){
char str[10];
int x;
stack<int> s;
scanf("%d",&n);
for(int i=0;i<2*n;i++){
scanf("%s",str);
if(strcmp(str,"Push")==0){ //突破点
scanf("%d",&x);
pre[num1++]=x;
s.push(x);
}else{
in[num2++]=s.top(); //取栈顶元素
s.pop();
}
}
node* root=create(0,n-1,0,n-1);
postOrder(root);
printf("\n");
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
int origin[105],target[105],a[105];
void print(int a[]){ //输出数组
for(int i = 0; i < n; i++){
if(i != 0)putchar(' ');
printf("%d", a[i]);
}
}
bool check(int a[]){ //判断数组相同函数
for(int i=0;i<n;i++){
if(a[i]!=target[i])
return false;
}
return true;
}
bool insertSort(){ //插入排序
bool flag=false;
copy(origin,origin+n,a);
for(int i=1;i<n;i++){
if(i!=1&&check(a))
flag=true;
sort(a,a+i+1);
if(flag){
return true;
}
}
return false;
}
bool mergeSort(){
bool flag=false;
copy(origin,origin+n,a);
for(int i=2;i/2<=n;i+=i){
for(int j=0;j<n;j+=i){
sort(a+j,a+min(i+j,n));
}
if(flag){
return true;
}
flag=check(a);
}
return false;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&origin[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&target[i]);
}
if(insertSort()){
printf("Insertion Sort\n");
print(a);
}
if(mergeSort()){
printf("Merge Sort\n");
print(a);
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main(){
int flag[130]={0},count1=0,count2=0;
string a,b;
bool tmp=true;
getline(cin,a);
getline(cin,b);
int len1=a.size();
int len2=b.size();
for(int i=0;i<len1;i++){
flag[a[i]]++;
}
for(int i=0;i<len2;i++){
flag[b[i]]--;
}
for(int i=0;i<130;i++){
if(flag[i]<0){
tmp=false;
flag[i]=-flag[i];
count2+=flag[i];
}else if(flag[i]>0){
count1+=flag[i];
}
}
if(tmp){
cout<<"Yes"<<" "<<count1<<endl;
}else
cout<<"No"<<" "<<count2<<endl;
return 0;
}
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
int origin[105],target[105],a[105];
void print(int a[]){ //输出数组
for(int i=1;i<=n;i++){
printf("%d",a[i]);
if(i<n)
printf(" ");
}
}
bool check(int a[]){ //判断数组相同函数
for(int i=1;i<=n;i++){
if(a[i]!=target[i])
return false;
}
return true;
}
bool insertSort(){ //插入排序
bool flag=false;
for(int i=2;i<n;i++){
if(i!=2&&check(a))
flag=true;
sort(a,a+i+1);
if(flag){
return true;
}
}
return false;
}
void downAdjust(int low,int high){ //向下调整
int i=low,j=2*i;
while(j<=high){
if(j+1<=high&&a[j+1]>a[j]){
j=j+1;
}
if(a[j]>a[i]){
swap(a[j],a[i]);
i=j;
j=2*i;
}else{
break;
}
}
}
void heapSort(){ //堆排序
bool flag=false;
for(int i=n/2;i>0;i--){
downAdjust(i,n);
}
for(int i=n;i>1;i--){
if(i!=n&&check(a)){
flag=true;
}
swap(a[i],a[1]);
downAdjust(1,i-1);
if(flag){
print(a);
return;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&origin[i]);
a[i]=origin[i];
}
for(int i=1;i<=n;i++)
scanf("%d",&target[i]);
if(insertSort()){
printf("Insertion Sort\n");
print(a);
}
else{
printf("Heap Sort\n");
for(int i=1;i<=n;i++){
a[i]=origin[i];
}
heapSort();
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int n,num[105],index=0;
struct node{
int data,lchild,rchild;
}Node[105];
void inOrder(int root){ //中序序列
if(root==-1)
return;
inOrder(Node[root].lchild);
Node[root].data=num[index++];
inOrder(Node[root].rchild);
}
void layerOrder(int root){ //层序遍历
queue<int> q;
q.push(root);
index=0;
while(!q.empty()){
int now=q.front();
q.pop();
printf("%d",Node[now].data);
index++;
if(index<n)
printf(" ");
if(Node[now].lchild!=-1){
q.push(Node[now].lchild);
}
if(Node[now].rchild!=-1){
q.push(Node[now].rchild);
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&Node[i].lchild,&Node[i].rchild);
for(int i=0;i<n;i++)
scanf("%d",&num[i]);
sort(num,num+n);
inOrder(0);
layerOrder(0);
printf("\n");
return 0;
}
#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
using namespace std;
string k[170]; //数字->火星文
map<string,int> mp; //火星文->数字
string a[13]={"tret","jan","feb","mar","apr","may","jun","jly","aug","sep","oct","nov","dec"};
string b[13]={"tret","tam","hel","maa","huh","tou","kes","hei","elo","syy","lok","mer","jou"};
void init(){
for(int i=0;i<13;i++){ //个位
k[i]=a[i];
k[i*13]=b[i];
mp[a[i]]=i;
mp[b[i]]=i*13;
}
for(int i=1;i<13;i++){
for(int j=1;j<13;j++){
string str=b[i]+" "+a[j];
k[i*13+j]=str;
mp[str]=i*13+j;
}
}
}
int main(){
init();
int n;
scanf("%d",&n);
cin.ignore(); //后面用getline,所以要清空cin流
while(n--){
string s;
getline(cin,s);
if(s[0]>='0'&&s[0]<='9'){
int temp=0;
for(int i=0;i<s.length();i++){
temp=temp*10+(s[i]-'0');
}
if(temp%13==0){ //注意13的倍数特殊情况
cout<<b[temp/13]<<endl;
}else
cout<<k[temp]<<endl;
}
else{
cout<<mp[s]<<endl;
}
}
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。