目录
题目一:
代码:
题目二:
代码:
题目三:
代码:
题目四:
代码:
题目五:
代码:
题目六:
代码:
题目七:
代码:
题目八:
代码:
题目九:
代码:
题目十:
代码:
题目一:
代码:
#include<iostream>
#include<map>
using namespace std;
int main()
{string s;map<char ,int>mp;cin>>s;for(int i=0;i<s.size();i++){mp[s[i]]++;//记录}if(mp.size()%2==1)//奇数cout<<"IGNORE HIM!"<<endl;elsecout<<"CHAT WITH HER!"<<endl;
}
题目二:
代码:
#include<iostream>
using namespace std;
int main()
{int a,b;int cnta=0,cntb=0;int aa,bb;cin>>a>>b;aa=a,bb=b;while(aa){if(aa%2==1)cnta++;//记录a的二进制1个数aa/=2;}//cout<<cnta;while(bb){if(bb%2==1)cntb++;//记录b的二进制1个数bb/=2;}// cout<<cntb;if(cnta>cntb)cout<<a;else if(cntb>cnta)cout<<b;elsecout<<max(a,b);
}
题目三:
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int n,k;cin>>n>>k;int a[10100];for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);//排序int i=0;k--;for(i=1;i<n;i++){if(a[i]!=a[i-1])//去重k--;if(k==0)break;}if(k<=n&&k==0)//k符合要求cout<<a[i]<<endl;elsecout<<"NO RESULT"<<endl;
}
题目四:
代码:
#include<iostream>//错排列
#include<cstring>
using namespace std;
int n;
int book[25];
int chosen[25];
int cnt=0;
void dfs(int k)//全排列模板
{if(k==n+1){//for(int i=1;i<=n;i++)//cout<<chosen[i]<<" ";//cout<<endl;cnt++;return ;}for(int i=1;i<=n;i++){if(book[i]||i==k)//跳过条件continue;book[i]=1;chosen[k]=i;dfs(k+1);book[i]=0;chosen[k]=0;}
}
long long j(int n)//阶乘
{long long cnt=1;for(int i=1;i<=n;i++){cnt*=i;}return cnt;
}
int main()
{int m;cin>>m;while(m--){cin>>n;if(n<=8)//列举10个,发现8个以后都为36.79{cnt=0;memset(book,0,sizeof(book));dfs(1);//cout<<cnt<<endl;long long ji=j(n);//cout<<ji;float ans=((cnt*1.0)/ji*1.0)*100;printf("%.2f%\n",ans);}elsecout<<"36.79%"<<endl;}
}
题目五:
代码:
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{int num,id;
};
int main()
{int n;cin>>n;node a[100010];for(int i=0;i<n;i++){cin>>a[i].num;a[i].id=i+1;}for(int i=0;i<n-1;i++)//冒泡排序for(int j=i+1;j<n;j++){if(a[i].num>a[j].num)swap(a[i],a[j]);}long long sum=0;for(int i=0;i<n;i++){sum+=(n-i)*a[i].num;//有n-i个人要等a[i].num时间cout<<a[i].id;if(i!=n-1)cout<<" ";}cout<<endl;float ans=sum*1.0/n;printf("%.2f",ans);}
题目六:
代码:
#include<iostream>//并查集
#include<vector>
using namespace std;
vector<vector<int>> g(1010);
int f[1010], cnt[1010];
int n;
int find(int x)//查找
{if (x == f[x])return x;return f[x] = find(f[x]);
}
void merge(int x, int y)//合并
{x = find(x), y = find(y);if (x != y){f[x] = y;cnt[y] += cnt[x];//加上分支个数}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){int k;cin >> k;while (k--){int x;cin >> x;g[i].push_back(x);}}for (int i = 1; i <= n; i++)//初始化{f[i] = i;cnt[i] = 1;}for (int i = n; i >= 1; i--)//从后往前合并{for (auto j : g[i])//遍历其边{if (j > i)//只合并与i相连且更大的点的边{merge(i, j);}if (cnt[find(i)] > n / 2)//找到大于n/2,即删掉这个点就第一次小于n/2{cout << i <<endl;return 0;}}}
}
题目七:
代码:
#include<iostream>
#include<map>
using namespace std;
int f[1010010], g[1010][1010];
int n, m;
int find(int x)//查找
{if (x == f[x]) return x;return f[x] = find(f[x]);
}
void merge(int x, int y)//合并
{x = find(x), y = find(y);if (x != y)f[x] = f[y];
}
int num(int x, int y)//序号
{return (x - 1) * m + y;
}
int main()
{cin >> n >> m;map<int, int> mp;long long ans = 0;int a1, a2, b1, b2;for (int i = 1; i <= n * m; i++)//初始化f[i] = i;while (cin >> a1 >> a2 >> b1 >> b2){if (a2 != b2)mp[min(a2, b2)] = 1;int a = num(a1, a2);int b = num(b1, b2);merge(a, b);}for (int i = 1; i < m; i++){if (!mp[i])//有一列没有,则需要加一个横向的2{ans += 2;int a = num(1, i);int b = num(1, i + 1);merge(a, b);//合并相邻的两列}}mp.clear();for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){mp[find(num(i, j))] = 1;}ans += mp.size() - 1;//多少个连通分支(只需要纵向相连)-1cout << ans << endl;
}
/*
a ab
ab b*/
题目八:
代码:
#include<iostream>//中位数
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int x,y;
};
bool cmp(node a,node b)
{return a.y<b.y;
}
int main()
{int n;node a[10100];cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}sort(a+1,a+1+n,cmp);//排序int mid=0;if(n%2==0)//找中位数序号mid=n/2;elsemid=n/2+1;long long sum=0;for(int i=1;i<=n;i++){sum+=abs(a[i].y-a[mid].y);}cout<<" "<<sum;
}
题目九:
代码:
#include<iostream>
using namespace std;
int main()
{long long ans=0;int n;cin>>n;for(int i=1;i<=n;i++){ans+=n/i;}cout<<ans<<endl;
}
/*
对于四来说,就是1、2、3、4的因子个数和看成1~4中是1的倍数的有几个
看成1~4中是2的倍数的有几个
看成1~4中是3的倍数的有几个
看成1~4中是4的倍数的有几个
*/
题目十:
代码:
#include<iostream>
using namespace std;
int g[110][110];
int dp[110][110];//dp存第x行第y列的最长路径
int n,m;
int len=0;
int maxx=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dfs(int x,int y)//深度搜索
{if(dp[x][y]!=0)return dp[x][y];int l=1;for(int i=0;i<4;i++)//查找四个方向,有没有大于的{int tx=dx[i]+x,ty=dy[i]+y;if(tx<1||ty<1||ty>m||tx>n||g[x][y]>=g[tx][ty])//边界条件continue;l=max(l,dfs(tx,ty)+1);//有大于的,则深度继续搜索}dp[x][y]=l;//dp存第x行第y列的最长路径return l;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>g[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){maxx=max(maxx,dfs(i,j));}cout<<maxx<<endl;
}