TODO 还没学明白 TEX 公式格式导出到博客时还要更改
[mathjax]
目录
展开
分治专题
1 快速幂 AC
将指数变成二进制数字，分别求每个 1 的结果
#include <cstdio>
typedef long long LL;
int to2(LL k,int result[]){
int count = 0;
while(k > 0){
result[count] = k % 2;
k >>= 1; // 向右移位
count ++;
}
return count;
}
int main(){
LL b,p,k;
int midres[32] = {};
scanf("%lld %lld %lld",&b,&p,&k);
LL finalres = 1;
int count = to2(p,midres);
LL num[32] = {b%k};
for(int i = 1;i<count;i++){
num[i] = num[i-1] * num[i-1] % k;
// printf("%d-%lld ",i,num[i]);
}
for(int i = 0;i<count;i++){
if(midres[i] == 1) {
finalres *= num[i];
finalres %= k;
}
}
// 最后需要再 %k 否则 84分 （反例：2 0 1）
printf("%lld^%lld mod %lld=%lld\n",b,p,k,finalres %k);
return 0;
}
看了大佬题解发现，自己很多空间都是多余的。最后只要一个计数的答案，因此中间结果并不需要记录下来：
// 大佬题解
#include <bits/stdc++.h>
using namespace std;
int main(){
long long ans=1,i,j,k,m,n,b,p;
scanf("%lld%lld%lld",&b,&m,&p);
printf("%lld^%lld mod %lld=",b,m,p);
while(m>0){
if(m%2==1)
ans=ans*b%p;
b=b*b%p;
m=m>>1;
}
printf("%lld",ans%p);
return 0;
}
2 幂次方 AC
分治，递归，主要是括号格式问题
# include <cstdio>
int mi[15] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};// 这里直接偷懒了
void devide(int n){
if(n == 2)printf("2");
else if (n == 4)printf("2(2)");
else{
int sgn = 0,never = 0;
for(int i = 14;i>=0;i--){
if (n >= mi[i] && n > 3){
if (sgn != 0)printf("+");
printf("2(");
devide(i);
printf(")");
n -= mi[i];
sgn ++;
}else if (n == 3){
if (sgn != 0)printf("+");
printf("2+2(0)");
n = 0;
sgn ++;
}else if (n == 2){
if (sgn == 0)printf("(2)");
else printf("+2");
n = 0;
sgn ++;
}else if (n == 1){
if(sgn > 0 && never == 0){
printf("+2(0)");
never = 1;
}
}
}
}
}
int main(){
int n;
scanf("%d",&n);
devide(n);
return 0;
}
对于这道题，一开始的几个不需要括号的我单独列出来了，而大佬救是不同凡响，一句话解决
大佬题解
#include<bits/stdc++.h>
using namespace std;
string run(int x,int i=0,string s=string("")){
if(x==0)return string("0");
do if(x&1)s=(i==1?"2":"2("+run(i)+")")+(s==""?"":"+")+s;//拼接字符串，应题意，要把低次方接在后面
while(++i,x>>=1);//每次向右移位
return s;
}
int main(){
int x;cin>>x;
cout<<run(x)<<endl;
}
3 逆序对
线段树 # TODO
· 在数组表示🌲的时候，通常左孩子 2*v 在代码中写成 v<<1；右孩子 2*v+1 写成 v<<1|1
4 画图
杨辉三角是真的秀。 常规方法：建一个 1024 * 2048 的 char 矩阵，将图腾先倒置处理，最后倒序输出。
递归专题
1 台阶问题 AC
# TEX 最原始的思路是 $(a_n = a_{n-1} + … + a_{n-k})$ 代码如下
# include <cstdio>
int n,k,solution[100001] = {1};
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++){
for(int j = i-k;j<i;j++){
if(j >= 0)
solution[i]=(solution[i] + solution[j])%100003;
}
}
// for(int i = 0;i<=n;i++){
// printf("%d ",solution[i]);
// }
printf("%d",solution[n]);
}
大佬的高级方法：
- 高级递归 O( n ) ： ( a_n = 2 * a_{n-1} – a_{i-k-1} )
- 矩阵乘法 O( n * logk )：设 n = 4，
$$\begin{matrix} let \quad A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix} &
B = \begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ a_{n-3} \end {bmatrix}\end{matrix}$$
那么
$$\begin{matrix} B &* &A &= &\begin{bmatrix} a_{n+1} \\ a_{n} \\ a_{n-1} \\ a_{n-2} \end {bmatrix} \end{matrix}$$
所以 $( a_n = (B * A^{n-k})[1] )$ ，此处就可以使用快速幂的方法
- 树状数组 O( n * logk )：树状数组可以解决的问题都可以用线段树解决，但是树状数组的系数要少很多
2 数的划分 AC
这个题做的太奇妙了，我都还没弄懂具体细节，写了个 dfs，题目样例对了，交上去竟然一次 AC
# include <cstdio>
int n,k;
int solu(int n,int k,int min){ // min 是本次子划分最小的数字
if (n == 1 || k == 1)return 1;
if (min > n)return 0;
int solution = 0;
for(int i = min;i<=n/k;i++){
// 每个划分都是从小到大划分
solution += solu(n-i,k-1,i);
}
return solution;
}
int main(){
scanf("%d%d",&n,&k);
printf("%d",solu(n, k, 1));
}
看到有人用 #include <bits/stdc++.h>，意思是包含所有的 C++ 头文件，百炼 OJ 亲测可用！然鹅本地 XCode 的 GCC 竟然不行==
3 传球游戏 AC
太爽了，又是一次 AC
# include <cstdio>
int main(){
int n,m;
scanf("%d%d",&n,&m);
int res[30][30] = {};
for(int i = 0;i<m;i++){
if(i == 0){
for(int j = 0;j<n;j++){
if (j == n-1 || j % n == 1)
res[i][j] = 1;
}
}else{
for(int j = 0;j<n;j++){
res[i][j] = res[i-1][(j+n-1)%n] + res[i-1][(j+n+1)%n];
}
}
}
// for(int i = 0;i<m;i++){
// for(int j = 0;j<n;j++){
// printf("%d ",res[i][j]);
// }
// printf("\n");
// }
printf("%d",res[m-1][0]);
return 0;
}
我的想法就是模拟一次次传播，看到一位大佬和我方法差不多，但是代码风格很新奇：
#include<bits/stdc++.h>
using namespace std;
int n,m,f[50][50];
int main()
{
cin>>n>>m;f[0][0]=1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(f[i][j])
f[i+1][(j-1+n)%n]+=f[i][j], // 后面是‘，’可以并列语句，少大括号。
f[i+1][(j+1)%n]+=f[i][j];
cout<<f[m][0];
return 0;
}
4 电梯 AC
DFS，有个小错找了好久。记得一定要回溯！不然本条路线的 vis 会被其它路线影响
# include <cstdio>
# include <vector>
# define min(x,y) x<y ? x : y
using namespace std;
vector<int>graph[205];
int vis[205] = {},ans = 0X7fffffff;
void DFS(int start,int step,int end){
// printf("%d - %d -\n",start,step);
if (start == end){
ans = step;
}
if (step >= ans); // 剪枝！
else if (graph[start].size() > 0){
vis[start] = 1;
for(int i = 0;i<graph[start].size();i++){
if (vis[graph[start][i]] == 0)
DFS(graph[start][i],step+1,end);
}
vis[start] = 0; // 回溯，否则其它并行道路会受当前道路的影响而走不通
}
}
int main(){
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
for(int i = 1;i<=n;i++){
int temp;
scanf("%d",&temp);
if (temp != 0){
if (i > temp)
graph[i].push_back(i - temp);
if (i + temp <= n)
graph[i].push_back(i + temp);
}
}
vis[a] = 1;
int step = 0;
DFS(a,step,b);
printf("%d",ans == 0X7fffffff?-1:ans);
return 0;
}
5 数字三角形 AC
这道题就是 POJ 2760，也是《引导》第十章第一题，当时做太难了，于是放弃了这本书，开始刷落谷的递归动态规划，没想到现在竟然秒杀。之前其实是粗心的错误，结点的父节点并不是 <<1，这不是二叉树！！
# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 1000001;
int main(){
int n,tri[maxn] = {},sum[maxn] = {};
scanf("%d",&n);
scanf("%d",&tri[1]);
sum[1] = tri[1];
int count = 2;
for(int i = 2;i<=n*(n+1)/2;i++){
scanf("%d",&tri[i]);
if (i != count*(count+1)/2 &&
i-1 != count*(count+1)/2){
int father = i - count*(count-1)/2 + (count-2)*(count-1)/2;
sum[i] = tri[i] + max(sum[father-1],sum[father]);
}
else if(i == count*(count+1)/2){
int father = count*(count-1)/2;
sum[i] = tri[i] + sum[father];
}
else if(i == count*(count+1)/2 + 1){
int father = count*(count-1)/2 + 1;
sum[i] = tri[i] + sum[father];
count ++;
}
}
// // 打印和三角
// count = 1;
// printf("\n");
// for(int i = 1;i<=n*(n+1)/2;i++){
// printf("%3d ",sum[i]);
// if(i == count*(count+1)/2){
// printf("\n");
// for(int j = 0;j<(n - count);j++){
// printf(" ");
// }
// count++;
// }
// }
// // 打印原三角
// count = 1;
// printf("\n");
// for(int i = 1;i<=n*(n+1)/2;i++){
// printf("%3d ",tri[i]);
// if(i == count*(count+1)/2){
// printf("\n");
// for(int j = 0;j<(n - count);j++){
// printf(" ");
// }
// count++;
// }
// }
int maxsum = sum[n*(n-1)/2];
for(int i = n*(n-1)/2;i<=n*(n+1)/2;i++){
maxsum = maxsum > sum[i]?maxsum:sum[i];
}
printf("%d",maxsum);
return 0;
}
然而大佬就厉害了：用一维数组做，妙哉！
首先是边读边做，第一层循环 i 从 n 到 1，第二层循环 j 从 i 到 n（为了每次都能取到上次的值）,每次读入一个变量 p，
状态转移方程：a[j] = max{a[j],a[j+1]}+p（a[j]表示走到第 i 层第 j 个时的最大值）。最后输出 a 数组的最大值即可。
下面我来用测试数据模拟一下 (注意：要开1002的数组，不然会越界)：
a[1] a[2] a[3] a[4] a[5] a[6]
初始化： 0 0 0 0 0 0
第一次： 0 0 0 0 7 0
第二次： 0 0 0 10 15 0
第三次： 0 0 18 16 15 0
第四次： 0 20 25 20 19 0
第五次： 24 30 27 26 24 0
代码（c/c++）：
#include<cstdio>
int n,a[1002],i,j,ans,p;
int max(int &x,int &y){return x>y?x:y;}
int main(){
scanf("%d",&n);
for(i=n;i;i--)
for(j=i;j<=n;j++)
scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
for(i=1;i<=n;i++)
ans=max(ans,a[i]);
printf("%d",ans);
return 0;
}
一些其他的没啥用的概念：
register关键字：请求编译器尽可能的将变量存在 CPU 内部寄存器中，而不是通过内存寻址访问，以提高效率。inline：用法
6 数字分段 TODO
7 丢瓶盖 TODO
这两题都是二分法
8 过河卒 AC
用DFS超时
# include <cstdio>
int m,n,x,y;
int g[21][21] = {},vis[21][21] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
bool legal(int x,int y){
if (x < 0 || y < 0 || x > m || y >n || g[x][y] || vis[x][y])return false;
return true;
}
void DFS(int i,int j){
vis[i][j] = 1;
if (i == m && j == n)res++;
else{
if (legal(i+1,j)) DFS(i+1,j);
if (legal(i,j+1)) DFS(i,j+1);
// if (legal(i-1,j)) DFS(i-1,j);
// if (legal(i,j-1)) DFS(i,j-1);
}
vis[i][j] = 0;
}
int main(){
scanf("%d %d %d %d",&m,&n,&x,&y);
g[x][y] = 1;
for (int i = 0;i<8;i++){
int nx = x+a[i][0],ny = y+a[i][1];
if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
g[nx][ny] = 1;
}
DFS(0,0);
printf("%d",res);
return 0;
}
递推 AC
// 2020-03-16 11:46:57
// https://www.luogu.com.cn/problem/P1002
# include <cstdio>
#include<algorithm>
using namespace std;
int m,n,x,y;
int g[30][30] = {},vis[30][30] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
unsigned long long f[30][30];
int main(){
scanf("%d %d %d %d",&m,&n,&x,&y);
g[x][y] = 1;
for (int i = 0;i<8;i++){
int nx = x+a[i][0],ny = y+a[i][1];
if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
g[nx][ny] = 1;
}
f[0][0] = 1;
for(int i = 0;i<=m;i++){
for(int j = 0;j<=n;j++){
if (g[i][j])continue;
f[i][j] = max(f[i][j],f[i-1][j]+f[i][j-1]);
}
}
printf("%lld",f[m][n]);
return 0;
}
9 出栈序列 AC
由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分
比x小
比x大
比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]
比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]
这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
另外，由于x有n个取值，所以
ans = f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0];
这，就是传说中的卡特兰数
# include <cstdio>
int n,f[20] = {1,1};
int main(){
scanf("%d",&n);
for(int i = 2;i<=n;i++){
for (int j = 0;j<i;j++){
f[i] += f[j] * f[i-j-1];
}
}
printf("%d",f[n]);
return 0;
}
10 数的计算 AC
我的方法过于暴力，但是也能过
# include <cstdio>
int n,f[1005] = {1};
int main(){
scanf("%d",&n);
for (int i = 1;i<=n;i++){
for(int j = 0;j<=i/2;j++){
f[i]+=f[j];
}
}
// 这里其实可以只算到 f[n/2]，最后输出累加和
printf("%d",f[n]);
return 0;
}
大佬的 DP 方法：
#include<cstdio>
using namespace std;
int main(){
int n,cnt=1,i,f[1010];
f[0]=f[1]=1;
scanf("%d",&n);
for(i=2;i<=n;i++){
if(i%2==0){
f[i]=f[i-1]+f[i/2];
}else{
f[i]=f[i-1];
}
}
printf("%d\n",f[n]);
}
11 蜜蜂采蜜 AC
看到范围 1000，用高精！
# 2020-03-17 09:58:32
inn = input().split(" ")
m = int(inn[0])
n = int(inn[1])
f = [0]*1005
f[m] = 1
for i in range(m+1,n+1):
f[i] = f[i-1] + f[i-2]
print(f[n])
12 铺瓷砖 AC
这种题考数学，写出前几项，找规律
# include <cstdio>
int n,f[1000000] = {0,1,2,5};
int main(){
scanf("%d",&n);
for (int i = 4;i<=n;i++){
f[i] = f[i-3]+ f[i-1]*2;
f[i] %= 10000;
}
printf("%d",f[n]);
return 0;
}
线性数据结构
1 报数淘汰 AC
非常简单的数组模拟
#include <cstdio>
int main(){
int n,m,count = 0,j = 0;
scanf("%d %d",&n,&m);
int vis[100] = {};
for(int i = 0;i<n;){
if (vis[j%n] == 0){
count ++;
}
if (count == m){
vis[j%n] = 1;
count = 0;
printf("%d",j%n + 1);
if (i < n-1)printf(" ");
i++;
}
j++;
}
return 0;
}
2 最大子段和 AC
#include <cstdio>
int main(){
int n,sum = 0,sgn = 0,max = -0x3fffffff;
scanf("%d",&n);
int a[n];
// 输入，并判断数列中是否有正数
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
if (a[i] > 0)sgn = 1;
max = max<a[i]?a[i]:max;
}
if (sgn == 0){ // 如果全为负，则选一个最大的
printf("%d",max);
return 0;
}else{ // 有正数，则挑选、舍弃
for(int i = 0;i<n;i++){
sum += a[i];
if (sum <= 0)sum = 0;
// printf("%d- ",sum);
max = max<sum?sum:max;
}
printf("%d",max);
return 0;
}
}
其中，第一次写的时候遗漏了最大和为负的情况，例如数据“1 -1”答案就不对，于是分类进行讨论
而大佬的方法就厉害了，先判断大于零，再加当前的数字，就能统一算法了！！
#include<cstdio>
int n,j,sum,maxx;
int main(){
scanf("%d%d",&n,&maxx);
sum=maxx;//输入n
while(--n){
scanf("%d",&j);
sum=sum>0?sum:0;
sum+=j;
maxx=maxx>sum?maxx:sum;
}//贪心，如果负了就舍去
return (printf("%d",maxx))&0;//输出并return 0
}
3 括号匹配 AC
送分题
#include<cstdio>
int main(){
int count = 0;
char ch;
while(1){
scanf("%c",&ch);
if (ch == '(')count ++;
else if(ch == ')')count --;
else if(ch == '@')break;
if (count < 0){
printf("NO");
return 0;
}
}
if (count == 0)printf("YES");
else printf("NO");
return 0;
}
4 链表优化 40 TLE TODO
我直接用的 stl 里面的 vector，我想不到有什么优化的方法。找的过程如果用 hashtable，可以缩短到 O(1) 时间找到，但是在插入的时候，hashtable 就要花费 O(n) 的时间来修改，我现在这样是花费多个 O(logn)，改 hash 难道不是得不偿失吗？
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int main(){
int n,m,lr,v;
vector<int>team(1,1);
scanf("%d",&n);
for(int i = 1;i<n;i++){
scanf("%d %d",&v,&lr);
team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);
}
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d",&v);
vector<int>::iterator res = find(team.begin( ), team.end( ), v);
if (res != team.end())
team.erase(res);
}
for(int i = 0;i<team.size();i++){
printf("%d",team[i]);
if(i != team.size()-1)printf(" ");
else printf("\n");
}
return 0;
}
5 后缀表达式 AC
一开始担心除法，用的 float，67分，改成 long long，AC
# include <cstdio>
# include <cstring>
# include <stack>
using namespace std;
long long calcu(long long b,long long a,char ch){
if (ch == '*')return a*b;
else if (ch == '/')return a/b;
else if (ch == '-')return a-b;
else return a+b;
}
int main(){
char ch;
int num = 0;
stack<long long>n;
while(1){
scanf("%c",&ch);
if (ch >= '0' && ch <= '9')
num = num * 10 + ch - '0';
else if (ch == '.') {
n.push(num);
num = 0;
}else if (ch == '@'){
break;
}else{
long long tempa = n.top();n.pop();
long long tempb = n.top();n.pop();
n.push(calcu(tempa,tempb,ch));
}
}
printf("%d",(int)n.top());
}
6 水list AC
# include <cstdio>
int a[2000001],n,m,d;
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++)scanf("%d",&a[i]);
for(int i = 0;i<m;i++){
scanf("%d",&d);
printf("%d\n",a[d-1]);
}
return 0;
}
7 map AC
hash 空间不够，改成 map
#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{
scanf("%d%d",&n,&q);
while(q--)
{
scanf("%d %d %d",&p,&i,&j);
if(p==1)
{
scanf("%d",&k);
b[i*1000000+j]=k;
}
else printf("%d\n",b[i*1000000+j]);
}
return 0;
}
8 模拟栈 AC
# include <cstdio>
# include <stack>
using namespace std;
int q,n;
stack<int>st;
int main(){
scanf("%d",&q);
for(;q;q--){
scanf("%d",&n);
int a[n+1],b[n+1];
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
for(int i = 0;i<n;i++){scanf("%d",&b[i]);}
int i = 0,j = 0;
for(;i<n;i++){
st.push(a[i]);
while (b[j] == st.top()){
st.pop();
j++;
if (st.empty())break;
}
}
if (st.size())printf("No\n");
else printf("Yes\n");
while (!st.empty())st.pop();
}
return 0;
}
🌲
1 FBI 树 AC
简单的二叉树概念题，递归建树，后序遍历
//data
//3
//10001011
// f
// f f
// f b f i
// i b b b i b i i
# include <cstdio>
# include <cmath>
using namespace std;
struct Node{
char value;
Node * lch;
Node * rch;
};
char getCh(char a[],int length){
int exist0 = 0,exist1 = 0;
for(int i = 0;i<length;i++){
if (a[i] == '1')exist1 ++;
else if (a[i] == '0')exist0 ++;
if (exist0 != 0 && exist1 != 0)return 'F';
}
if (exist1 == 0 && exist0 != 0)return 'B';
else if (exist0 == 0 && exist1 != 0)return 'I';
else return 'F';
}
void cutChar(char ch[],char newch[],int start,int afterlen){
for(int i = 0;i<afterlen;i++){
newch[i] = ch[start + i];
}
newch[afterlen] = '\0';
// printf("= %d ",afterlen);
// for(int i = 0;i<afterlen;i++){
// printf("%c",newch[i]);
// }
// printf("\n");
}
Node *generateTree(char ch[],int n){
if (n == -1)return NULL;
int length = pow(2,n);
Node *root = new Node;
root -> value = getCh(ch, length);
// printf("=== ch->%s\n",ch);
// printf("=== root -> %c \n",root->value);
char newchl[(length/2)+1],newchr[(length/2)+1];
cutChar(ch, newchl, 0, (length/2));
cutChar(ch, newchr, (length/2), (length/2));
root -> lch = generateTree(newchl, n-1);
root -> rch = generateTree(newchr, n-1);
return root;
}
void backOrder(Node *root){
if (root == NULL)return;
backOrder(root->lch);
backOrder(root->rch);
printf("%c",root->value);
}
int n,length = 1;
int main(){
scanf("%d",&n);
length <<= n;
char ch[length+1];
scanf("%s",ch);
Node *root = generateTree(ch,n);
backOrder(root);
return 0;
}
但是看了大佬题解，发现自己的想法有多处冗余：
- 建树传参时，无需每次都新建子串。只需要每次规定子串的起始位置，随机访问即可；
- 判断 FBI 时，
if (exist1 == 0 && exist0 != 0)直接写为if (exist0)就够了（本来前半段也是冗余的） - 建树和后序遍历可以在同一个递归中完成，即在当前函数里，先遍历建树，再打印
root->value；也可以是在后序遍历的过程中加一些操作。
参考代码如下两种：
#include <iostream>
using namespace std;
char s[1050];
void maketree(int x,int y){ // 此函数是在建树的模板上改的
if(y>x){
maketree(x,(x+y)/2);
maketree((x+y+1)/2,y);
}
int B=1,I=1;
for(int i=0;i<=y-x;i++){
if(s[x+i]=='1') B=0;
else if(s[x+i]=='0') I=0;
}
if(B) cout<<'B';
else if(I) cout<<'I';
else cout<<'F';
}
int main() {
int n;
cin>>n>>s;
maketree(0,(1<<n)-1);
return 0;
}
#include <iostream>
#include <string>
using namespace std;
char FBI(string s) // 此函数是在后序遍历模板的基础上改的
{
if (s.length() > 1)
{
cout << FBI(s.substr(0, s.length()/2));
cout << FBI(s.substr(s.length()/2, s.length()/2));
}
if (s == string(s.length(), '0')) return 'B';
if (s == string(s.length(), '1')) return 'I';
return 'F';
}
int main()
{
int n;
cin >> n;
string s;
cin >> s;
cout << FBI(s);
return 0;
}
另外有个小技巧：
在输入长串的时候，写 A+1 就能从 A[1] 开始输入了： scanf("%s", A+1);； 此时若想测长度，则需要用 strlen(A+1)
本题还有一个很巧的想法：
- 直接将 0101 字符串转换为 BIBI 字符串，0->b，1->i
- 倒着建树：一开始字符串为叶节点，父节点的 FBI 可以根据两个孩子直接决定（妙），这样每一层一个字符串，直接合并，就是完全二叉树的层序遍历
- 后序遍历，按照下标访问完全二叉树的元素即可
- 以上想法其实就是线段树的想法 = =
☆ 很多🌲的题目根本不需要事实上把🌲建出来！
2 中序 + 后序 求先序 AC
基础送分题
# include <cstdio>
# include <iostream>
# include <string>
using namespace std;
struct Node{
char v;
Node* lch;
Node* rch;
};
Node* buildtree(string inorder,string backorder){
Node* root = new Node;
int size = (int)backorder.size() - 1;
root -> v = backorder[size];
root -> lch = root -> rch = NULL;
string::size_type pos = inorder.find(root -> v);
if (pos != string ::npos){
if (pos > 0)
root -> lch = buildtree(inorder.substr(0,pos), backorder.substr(0,pos));
if (size - pos > 0)
root -> rch = buildtree(inorder.substr(pos+1,size - pos), backorder.substr(pos,size - pos));
}
return root;
}
void forthOrder(Node *root){
if (root == NULL)return;
printf("%c",root->v);
forthOrder(root->lch);
forthOrder(root->rch);
}
int main(){
string inorder,backorder;
cin>>inorder>>backorder;
Node* root = buildtree(inorder,backorder);
forthOrder(root);
return 0;
}
但是为什么我的代码就要 40 行，大佬的代码只要 20 行呢？
先附上大佬的代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
if (in.size()>0){
char ch=after[after.size()-1];
cout<<ch;//找根输出
int k=in.find(ch);
beford(in.substr(0,k),after.substr(0,k));
beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；
}
}
int main(){
string inord,aftord;
cin>>inord;cin>>aftord;//读入
beford(inord,aftord);cout<<endl;
return 0;
}
对比发现有如下原因：
- 只需要一轮递归：在前序遍历的基础上更改即可
- 根本不需要真正建树，只需要递归输出
root即可 - 变量和函数名，在能表示意义的前提下，越短越好
3 新二叉树 AC
送分题，记住二叉树模板，按照规则建树即可
# include <cstdio>
# include <iostream>
# include <cstring>
using namespace std;
struct Node{
char c;
Node* l = NULL;
Node* r = NULL;
};
Node* newNode(char a){
Node* root = new Node;
root -> c = a;
root -> l = root -> r = NULL;
return root;
}
Node* create(char a,char b,char c){
Node* root = new Node;
Node* lc = new Node;
Node* rc = new Node;
root -> c = a;
if (b != '*'){
lc -> c = b;
root -> l = lc;
}
if (c != '*'){
rc -> c = c;
root -> r = rc;
}
return root;
}
void insert(Node* now,char a,char b,char c){
if(now == NULL)return;
else if(now -> c == a){
if (b != '*') now -> l = newNode(b);
if (c != '*') now -> r = newNode(c);
}else{
insert(now -> l, a, b, c);
insert(now -> r, a, b, c);
}
}
void forthOrder(Node *root){
if (root == NULL)return;
printf("%c",root->c);
forthOrder(root->l);
forthOrder(root->r);
}
int main(){
int n;
scanf("%d\n",&n);
char a,b,c;
scanf("%c%c%c\n",&a,&b,&c);
Node* root = create(a,b,c);
for(int i = 1;i<n-1;i++){
scanf("%c%c%c\n",&a,&b,&c);
insert(root,a,b,c);
}
scanf("%c%c%c",&a,&b,&c);
insert(root,a,b,c);
forthOrder(root);
return 0;
}
但是实际上，仍然，“很多🌲的题目根本不需要事实上把🌲建出来”：
#include<iostream>
#include<string>
#include<cstring>//不加会CE
using namespace std;
int n;
string s;
int main()
{
cin>>n;
cin>>s;
for(int i=2;i<=n;++i)//由于第一个为原串，所以单独输入
{
string ss;//前序遍历序列
cin>>ss;
int x=s.find(ss[0]);//找到这个子树的根节点在原串中的位置
s.erase(x,1);//清除根节点
s.insert(x,ss);//加入子树
}
for(int i=0;i<s.size();++i)
if(s[i]!='*') cout<<s[i];//不输出空节点
else continue;
}
或者树，直接用 n*3 的二维数组来存储：
#include<bits/stdc++.h>
using namespace std;
int n;
char a[30][3];
void f(char x)
{
if(x!='*')
{
cout<<x;
for(int i=1;i<=n;i++)
if(a[i][0]==x)
{
f(a[i][1]);
f(a[i][2]);
}
}
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i][0]>>a[i][1]>>a[i][2];
f(a[1][0]);
return 0;
}
而这个方法可以有改进：
先补充一下 map：
- map第一个好处是作为一个数组，可以开很大！比如：
map<int,int>x;，可以把x数组当成普通数组用，不过要注意一点：定义了x数组后，就不能使用c++的数组函数，比如memset - map第二个好处下标不一定是一个整数，可以甚至可以是一个字符串！
map<下标类型,数值类型>;比如：map<string,char>a; string st="123"; a[st]='1'; - map不仅可以开一维数组，还可以开二维数组。比如：
map<int,map<int,int>;注意这里是一定要有空格的，否则会编译错误
于是，此题可以用 map + 并查集解决（就不用了 O(n) 寻找了）：
#include <bits/stdc++.h>
using namespace std;
map<char,char>x;//用map来记录一个节点的左儿子
map<char,char>y;//用map来记录一个节点的右儿子
char a[35];//节点
void find(char ch){//并查集
cout<<ch;
if(x[ch]!='*')find(x[ch]);
if(y[ch]!='*')find(y[ch]);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char left,right;
cin>>a[i]>>left>>right;
x[a[i]]=left;
y[a[i]]=right;
}find(a[1]);//开始遍历整棵树
return 0;//结束程序
}
4 对称二叉树 52
思路有错，懒得继续改了
# include <cstdio>
# include <string>
# define maxn 1000001
using namespace std;
int n;
int tree[maxn][3],childnum[maxn];
string tempa,temp2;
bool c(int i){
printf("%d",i);
int l = tree[i][1],r = tree[i][2];
while(1){
if (tree[l][1] != -1 && tree[r][2] != -1){
l = tree[i][1];
r = tree[i][2];
}else if (tree[l][1] == -1 && tree[r][2] == -1){
return 1;
}else return 0;
}
}
int check(int i){ // 如果是平衡，返回孩子个数，如果不平衡，返回-1
if (tree[i][1] != -1 && tree[i][2] != -1){
// 两边均有孩子
if (tree[tree[i][1]][0] == tree[tree[i][2]][0]){
// 两边均有孩子，且左右孩子相等
int a,b;
a = check(tree[i][1]);
b = check(tree[i][2]);
if (c(i) && a == b && b >= 0){
// 两边均有孩子，且左右子树相等，且左右孩子均为对称
childnum[i] = a * 2 + 2;
return a * 2 + 2;
}else {
// 两边均有孩子，且左右子树相等，但左右孩子不均为对称
childnum[i] = -1;
return -1;
}
}
else {
// 两边均有孩子，但左右孩子不相等
childnum[i] = -1;
return -1;
}
}
else if (tree[i][1] == -1 && tree[i][2] == -1){
// 叶节点
childnum[i] = 0;
return 0;
}
else {
// 仅一边有孩子
childnum[i] = -1;
return -1;
}
}
int main(){
scanf("%d",&n);
if (n == 0){
printf("0");
return 0;
}
for(int i = 1;i<=n;i++){
scanf("%d",&tree[i][0]);
childnum[i] = -2;
}
for(int i = 1;i<=n;i++){
scanf("%d %d",&tree[i][1],&tree[i][2]);
}
for(int i = 1;i<=n;i++){ // 检查每个节点
check(i);
}
int max = 0;
for(int i = 1;i<=n;i++){
// printf("%d,",childnum[i]);
max = max>childnum[i]?max:childnum[i];
}
printf("%d",max+1);
return 0;
}
4 先序+中序 求后续 AC
其实也是不用建树的
# include <cstdio>
# include <cstring>
using namespace std;
char before[30],inorder[30];
struct node{
char c;
node* l;
node* r;
}*root;
node* get(char ll[],char in[]){
node *root;
root = new node;
root -> c = ll[0];
root -> l = NULL;
root -> r = NULL;
int i = 0;
for(;i<strlen(in);i++){
if (in[i] == ll[0])break;
}
char a[30] = {},b[30] = {},c[30] = {},d[30] = {};
for(int j = 1;j<i+1;j++)a[j-1] = ll[j];
for(int j = i+1;j<strlen(ll);j++)b[j-i-1] = ll[j];
for(int j = 0;j<i;j++)c[j] = in[j];
for(int j = i+1;j<strlen(in);j++)d[j-i-1] = in[j];
if(strlen(a) > 0)root -> l = get(a,c);
if(strlen(b) > 0)root -> r = get(b,d);
return root;
}
void postorder(node *root){
if (root -> l != NULL)postorder(root->l);
if (root -> r != NULL)postorder(root->r);
printf("%c",root->c);
}
int main(){
scanf("%s %s",inorder,before);
root = get(before,inorder);
postorder(root);
printf("\n");
return 0;
}
背包问题
模板
- 01 背包：n 件物品，背包容量 V，第 i 件物品费用 w[i]，价值 v[i]
for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);初始化：- 恰好装满背包：
f[0] = 0;f[1] = ... = f[V] = -∞; - 无需恰好装满：
f[0] = f[1] = ... = f[V] = 0;
- 恰好装满背包：
- 完全背包：n 种物品，每种无限个，背包容量 V，第 i 件物品费用
w[i]，价值v[i]- 转换为 01 背包：第 i 种物品拆成费用为
w[i]∗2^k、价值为v[i]∗2^k的若干件物品，即每种物品拆成log(V/w[i])件物品 - O(VN) 的算法：
for (int i = 1; i <= n; i++) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);
- 转换为 01 背包：第 i 种物品拆成费用为
- 多重背包问题：有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 p[i] 件可用，每件费用是 w[i]，价值是 v[i]转化为 01 背包问题
for (int i = 1; i <= n; i++) { int num = min(p[i], V / w[i]); for (int k = 1; num > 0; k <<= 1) { if (k > num) k = num; num -= k; for (int j = V; j >= w[i] * k; j--) f[j] = max(f[j], f[j - w[i] * k] + v[i] * k); } } - 混合背包问题：综合起来
p[i]:每个物品的件数，0代表无穷个 for (int i = 1; i <= n; i++) if (p[i] == 0) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]); else for (int k = 1; k <= p[i]; k++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]); - 二维背包问题：
for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) for (int k = T; k >= g[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]); - 分组背包问题：有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
for (所有的组k) for (int j = V; j >= 0; j--) for (所有属于组k的i) f[j] = max{f[j], f[j - w[i]] + v[i]}
1 01背包 AC
# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 30001;
int main(){
int n,m;
int a[maxn],b[maxn] = {},f[maxn] = {};
scanf("%d %d",&n,&m);
for(int i = 0;i<m;i++){
scanf("%d %d",&a[i],&b[i]);
b[i] *= a[i];
}
for(int i = 0;i<m;i++){
for(int j = n;j>=a[i];j--){
f[j] = max(f[j],f[j-a[i]] + b[i]);
}
}
printf("%d",f[n]);
return 0;
}
2 小A点菜 AC
见题解： https://www.luogu.com.cn/blog/user23325/solution-p1164
# include <cstdio>
int count = 0,n,m,a[10001] = {},f[101][10001]={0};
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;++i)
for(int j = 1;j<=m;++j)
{
// 为了第一个考虑，故 i 从 1 开始
if(j==a[i])f[i][j]=f[i-1][j]+1;
if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
if(j<a[i]) f[i][j]=f[i-1][j];
}
printf("%d",f[n][m]);
return 0;
}
贪心
1 合并果子 AC
用优先级队列，当下最小的两个
# include <cstdio>
# include <queue>
using namespace std;
int main(){
int n,temp,res = 0;
scanf("%d",&n);
priority_queue<int, vector<int>, greater<int> >pq;
for(int i = 0;i<n;i++) {
scanf("%d",&temp);
pq.push(temp);
}
while(pq.size() > 1){
int a = pq.top();pq.pop();
int b = pq.top();pq.pop();
int c = a + b;
res += c;
pq.push(c);
}
printf("%d",res);
return 0;
}
2 数列分段Section I AC
水
# include <cstdio>
int main(){
int n,m,count = 0,now = 0,temp;
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
scanf("%d",&temp);
if(now + temp > m){
count++;
now = temp;
}else{
now += temp;
}
}
printf("%d",count+1);
return 0;
}
3 混和牛奶 AC
# include <cstdio>
# include <queue>
using namespace std;
struct milk{
int volume,price;
friend bool operator < (milk m1,milk m2){
return m1.price > m2.price;
}
milk(int _p,int _a):volume(_a),price(_p){};
};
int main(){
int n,m,p,a,res = 0;
priority_queue<milk>pq;
scanf("%d%d",&n,&m);
for(int i = 0;i<m;i++){
scanf("%d%d",&p,&a);
pq.push(milk(p,a));
}
while(n > 0){
milk now = pq.top();
if (n > now.volume){
res += (now.volume * now.price);
pq.pop();
n -= now.volume;
}else{
res += (n * now.price);
break;
}
}
printf("%d",res);
return 0;
}
4 排队接水 AC
总时间要用 long long，相等时按序号排序
# include <cstdio>
# include <queue>
using namespace std;
struct s{
int n,i;
s(int _n,int _i):n(_n),i(_i){};
friend bool operator < (s s1,s s2){
if (s1.n != s2.n) return s1.n > s2.n; // 平
else return s1.i > s2.i;
}
};
int main(){
int n,temp;
long long res = 0; // int 不行
priority_queue<s>pq;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&temp);
pq.push(s(temp,i+1));
}
for(int j = 0;j<n;j++){
s now = pq.top();
printf("%d",now.i);
res += (n-j-1) * now.n;
pq.pop();
if (j < n-1) printf(" ");
else printf("\n");
}
printf("%.02lf\n",(double)res/n); // float 不行
return 0;
}
还有一个好方法，不需优先队列或结构体排序：
因为 n <= 1000，所以给每个 ti 都 * 1001，在加上当前序号，可以保证排序的时候序号不干扰排序，又可以方便输出序号（只需 mod 1001 输出序号，／1001 输出时间）
5 纪念品分组 AC
# include <cstdio>
# include <algorithm>
using namespace std;
bool cmp(int a,int b){return a>b;}
int main(){
int w,n,a[50001] = {};
scanf("%d%d",&w,&n);
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
sort(a, a+n, cmp);
for(int i = 0;i<n-1;i++){
// printf("%d ",a[i]);
if (a[n-1] + a[i] <= w)n--;
}
printf("%d",n);
return 0;
}
6 线段覆盖 AC
每个线段按结束点从小到大排序，按照这个顺序贪心放置即可
# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
struct test{
int begin,end;
test(int _begin,int _end):begin(_begin),end(_end){};
};
bool cmp(test a,test b){
return a.end < b.end;
}
int main(){
int n;
scanf("%d",&n);
vector<test>lst;
for(int i = 0;i<n;i++){
int b,e;
scanf("%d %d",&b,&e);
lst.push_back(test(b,e));
}
int count = 0,nowend = 0;
sort(lst.begin(),lst.end(),cmp);
for(int i = 0;i<n;i++){
if (lst[i].begin >= nowend){
nowend = lst[i].end;
count ++;
}
}
printf("%d",count);
return 0;
}
7 移动纸牌 AC
第一堆只能从第二堆索取或者给予，满足第一堆后，就可以删去这一堆，以此类推，删去所有堆
# include <cstdio>
int main(){
int n,sum = 0;
int a[101] = {};
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%d",&a[i]);
sum += a[i];
}
int avg = sum/n,count = 0;
for (int i = 0;i<n;i++)a[i] -= avg;
for (int i = 0;i<n;i++){
if (a[i] != 0){
a[i+1] += a[i];
count ++;
}
}
printf("%d",count);
return 0;
}
8 高精度 AC
高精度直接用 python！同时注意 // 的使用
n = int(input())
king = input().split()
a = []
for i in range(n):
k = input().split()
a.append([int(k[0]),int(k[1])])
# print(a,king)
a.sort(key = lambda x:x[0]*x[1])
maxsum = 0;product = int(king[0])
for i in a:
now = product//i[1]
# // 用来求商，要比除法再取整快得多！
if now>maxsum:
maxsum = now
product = product * i[0]
print(int(maxsum))
9 水题 AC
# include <cstdio>
int n,en = 0;
int a[1002][1002] = {};
int sumx[1002] = {},sumy[1002] = {};
struct empty{
int x,y;
empty(){};
empty(int _x,int _y):x(_x),y(_y){}
}e[10002];
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
scanf("%d",&a[i][j]);
if (!a[i][j])e[en++] = empty(i,j);
else{
sumx[i] += a[i][j];
sumy[j] += a[i][j];
}
}
}
int max = 0;
if (en == 0)printf("Bad Game!");
else{
for(int i = 0;i<en;i++){
int t = sumx[e[i].x] + sumy[e[i].y];
if (t > max)max = t;
}
printf("%d",max);
}
return 0;
}
10 水题 AC
# include<cstdio>
long long n,x,a[100005] = {};
int main(){
scanf("%lld %lld",&n,&x);
for(int i = 1;i<=n;i++)scanf("%lld",&a[i]);
long long res = 0;
for(int i = 1;i<=n;i++){
if (a[i] + a[i-1] > x){
long long p = a[i] + a[i-1] - x;
a[i] -= p;
res += p;
}
}
printf("%lld",res);
return 0;
}
11 铺设道路 AC
# include <cstdio>
int n,a[100005] = {};
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
int finish = 1,count = 0;
while (finish){
int start = 0,minn = 0,sgn = 0;
for(int i = 1;i<=n+1;i++){
if (a[i]){
sgn ++;
if(a[i-1]){
minn = minn<a[i]?minn:a[i];
}else{
start = i;
minn = a[i];
}
}else{
if(a[i-1]){
count+= minn;
for (int p = start;p<i;p++)a[p]-=minn;
}
}
}
// for (int i = 1;i<=n;i++)printf("%d ",a[i]);
// printf("%d\n",count);
if (sgn == 0)break;
}
printf("%d",count);
}
并查集
1 联通
并查集 + Kruskal：按照时间从小到大排序，每修一条路，如果这条路的两端本身 father 不同（即不连通），则联通的区域数 -1，当联通区域数 == 1 时，则成功
# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
int n,m,f,t,l,father[1002] = {};
struct road{
int from,to,length;
road(int _f,int _t,int _l):from(_f),to(_t),length(_l){}
};
bool cmp(road a,road b){
return a.length < b.length;
}
int findfather(int n){
while(n!=father[n]){n = father[n];}
return n;
}
void printfather(){
for(int i = 0;i<5;i++)printf(":%d",father[i]);
printf("\n");
}
int main(){
scanf("%d %d",&n,&m);
vector<road>a;
for(int i = 0;i<m;i++){
scanf("%d %d %d",&f,&t,&l);
a.push_back(road(f,t,l));
}
sort(a.begin(),a.end(),cmp);
for(int i = 0;i<n+1;i++) father[i] = i;
for(int i = 0;i<m;i++){
int fa = findfather(a[i].to),fb = findfather(a[i].from);
if (fa!=fb){
father[fa] = fb;
n --;
if (n == 1){
printf("%d",a[i].length);
return 0;
}
}
// printfather();printf("%d",n);
}
printf("-1");
return 0;
}
2 种类并查集 100
种类并查集，两种，开二倍数组
初始化：
fa[i] = i;
fa[i + n] = i + n;
关键步骤：
s[s[x+n]]=s[y];
s[s[x]]=s[y+n];
同时，此题的路径压缩也是非常之妙
// 2020-02-23 17:05:59
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,m,fa[40005] = {};
struct edge{
int a,b,value;
edge(int _a,int _b,int _v):a(_a),b(_b),value(_v){}
};
bool cmp(edge a,edge b){
return a.value>b.value;
}
int findfa(int n){
if (fa[n] == n) return n;
return fa[n] = findfa(fa[n]); // 路径压缩，妙！
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
fa[i] = i;
fa[i + n] = i + n; // 种类并查集，两种，开两倍容量数组？
}
int tempa,tempb,tempv;
vector<edge>lst;
for(int i = 0;i<m;i++){
scanf("%d %d %d",&tempa,&tempb,&tempv);
lst.push_back(edge(tempa,tempb,tempv));
}
sort(lst.begin(),lst.end(),cmp);
for(int i = 0;i<m;i++){
if (findfa(lst[i].a) == findfa(lst[i].b) || findfa(lst[i].a + n) == findfa(lst[i].b + n)){
printf("%d",lst[i].value);
return 0;
}
// 以下两步为种类并查集的关键步骤
fa[fa[lst[i].a + n]] = fa[lst[i].b];
fa[fa[lst[i].a]] = fa[lst[i].b + n];
}
printf("0");
return 0;
}
3 种类并查集 AC
同上，这里的写法终于让我明白了：
- 由于有压缩路径，所以
fa[n]和findfa(n)是等价的 - 谁是谁的爸爸都可以，因此本题解这样写也是可以滴，以后就以这个为准：
if (不同类){
fa[findfa(ta + n)] = findfa(tb);
fa[findfa(tb + n)] = findfa(ta);
}else if (同类){
fa[findfa(ta)] = findfa(tb);
}
// 2020-02-23 21:31:50
# include <cstdio>
# include <iostream>
//# include <vector>
//# include <algorithm>
using namespace std;
int n,m,fa[2502] = {};
int findfa(int n){
// 两种不同的路径压缩
// 1
// if(fa[n] == n)return n;
// return fa[n] = findfa(fa[n]);
// 2
if (fa[n] != n) fa[n] = findfa(fa[n]);
return fa[n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
fa[i] = i;fa[i+n] = i+n;
}
for(int i = 0;i<m;i++){
char c;
int ta,tb;
cin>>c>>ta>>tb;
// scanf("%*c%c %d %d",&c,&ta,&tb); //%*c是上一行的换行，为什么这个就不行？？#TODO
if (c == 'E'){
fa[findfa(ta + n)] = findfa(tb);
fa[findfa(tb + n)] = findfa(ta);
}else if (c == 'F'){
fa[findfa(ta)] = findfa(tb);
}
}
int s=0;
for(int i=1;i<=n;i++){
if(fa[i]==i) s++; //找有多少祖先，就是有多少团伙
}
printf("%d",s);
return 0;
}
4 种类并查集 AC
三类，就开三倍的数组并查集：
捕食的关系这样维护：
若是同类，则 `x+n*k & y+n*k` 共父
若 x 吃 y，则 `x + n*k & y + n*(k-1)` 共父
前面如果用了 find()，那么后面可以直接用 f[]
# include <cstdio>
int n,k,f[150005];
int find(int x){
if (x == f[x])return x;
return f[x] = find(f[x]);
}
int main(){
scanf("%d %d",&n,&k);
int x,y,z,count = 0;
for(int ii = 1;ii<=n*3;ii++)f[ii] = ii;
for(;k;k--){ //循环的简单写法
scanf("%d %d %d",&z,&x,&y);
// printf("%d\%d\%d-",z,x,y);
if (x > n || y > n){count ++;continue;}
else{
if (z == 1){
if (find(x+n) == find(y) || find(x) == find(y+n)){
// if (x != y){
count ++;continue;
// }
}else{
f[find(x)] = find(y);
f[find(x+n)] = find(y+n);
f[find(x+n+n)] = find(y+n+n);
}
}else {
// if (x == y){count ++;continue;}// 多余的
if (find(x) == find(y) || find(x) == find(y+n)){
count ++;continue;
}else{
f[find(x)] = find(y+n+n);
f[find(x+n)] = find(y);
f[find(x+n+n)] = find(y+n);
}
}
}
}
printf("%d\n",count);
return 0;
}
5 a bug’s life
18 保研机试原题 没有 oj 也不知道对错
// 2020-02-24 11:11:14
# include <cstdio>
int t,m,n,a,b,f[4005] = {};
int find(int n){
if (n == f[n])return n;
return f[n] = find(f[n]);
}
int main(){
scanf("%d",&t);
for(int p = 1;p <=t;p++){
int isfound = 0;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n*2;i++)f[i] = i;
for(;m;m--){
scanf("%d %d",&a,&b);
// printf("%d-%d-%d-%d-%d-%dmm\n",a,b,f[a],f[b],f[a+n],f[b+n]);
if (find(a) == find(b) || find(a+n) == find(b+n))
isfound = 1;
else{
f[f[a]] = f[b+n];
f[f[b]] = f[a+n];
}
// printf("%d-%d-%d-%d-%d-%dmmhh\n",a,b,f[a],f[b],f[a+n],f[b+n]);
}
if (isfound)printf("Scenario #%d:\nSuspicious bugs found!",p);
else printf("Scenario #%d:\nNo suspicious bugs found!",p);
}
return 0;
}
6 变性并查集 TODO
太烦了 懒得改了
# include <iostream>
using namespace std;
const int maxn = 30000;
int t,x,y,f[maxn+1],l[maxn+1] = {},u[maxn+1] = {};
// f 是 father；l 是当前位于第几层，0为队首；u 是该节点下面有多少个；
char c;
int find(int x){
if (x == f[x])return x;
else return f[x] = find(f[x]);
}
// 在寻找祖宗的同时，更新各个长辈的层数
int findandplus(int x,int y){
l[x] = l[x] + l[y] + 1;
if (x == f[x])return x;
else return f[x] = findandplus(f[x],y);
}
// 返回同一队列中两点之间的距离
int getlength(int x,int y){
int xx = l[x],yy = l[y];
return (xx>yy)?(xx-yy):(yy-xx);
}
int main(){
std::ios::sync_with_stdio(false);
cin>>t;
for(int i = 0;i<=maxn;i++)f[i] = i;
for(;t;t--){
cin>>c>>x>>y;
if (c == 'M'){
f[findandplus(x,y)] = y;
}else{
if (find(x) != find(y)) cout<<"-1"<<endl;
else {
cout<<getlength(x,y)-1<<endl;
}
}
for(int i = 1;i<10;i++){
printf("%d-%d ",f[i],l[i]);
}printf("\n");
}
return 0;
}
//6
//M 2 3
//C 1 2
//M 2 4
//C 4 2
//M 6 5
//M 3 5
7 并查集模板题 AC
# include <cstdio>
int fa[20001] = {};
int m,n,a,b,c;
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
void p(){
for(int i = 0;i<=n;i++)printf("%d ",fa[i]);
printf("\n");
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<=n;i++)fa[i] = i;
for(;m;m--){
scanf("%d %d %d",&a,&b,&c);
if (a == 1)fa[find(c)] = find(b);
else {
if (find(c) == find(b))printf("Y\n");
else printf("N\n");
}
// p();
}
return 0;
}
8 亲戚 AC
# include <cstdio>
int fa[5005] = {},n,m,p,a,b;
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
int main(){
scanf("%d %d %d",&n,&m,&p);
for(int i = 0;i<=n;i++)fa[i] = i;
for(;m;m--){
scanf("%d %d",&a,&b);
fa[find(a)] = find(b);
}
for(;p;p--){
scanf("%d %d",&a,&b);
if (find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
9 奶酪联通 AC
# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;
int t,n,h,r,a,b,c;
int fa[1002] = {};
struct point{
int x,y,z;
point(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
};
vector<point>v;
vector<int>top,bottom;
bool neighbour(point a, point b,int r){
return pow((a.x-b.x), 2)+pow((a.y-b.y), 2)+pow((a.z-b.z), 2) <= pow(r * 2.0,2);
}
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
int main(){
scanf("%d",&t);
for(;t;t--){
scanf("%d %d %d",&n,&h,&r);
v.clear();
bottom.clear();
top.clear();
v.push_back(point(0,0,0));
for(int i = 0;i<=n;i++)fa[i] = i;
for(int i = 1;i<=n;i++){
scanf("%d %d %d",&a,&b,&c);
v.push_back(point(a,b,c));
if (c <= r)bottom.push_back(i);
if (c + r >= h)top.push_back(i);
for(int j = 1;j<i;j++){
if (neighbour(v[j], v[i], r))fa[find(i)] = find(j);
}
}
// for(int i = 0;i<=n;i++)printf("%d ",fa[i]);
// printf("\n");
int sgn = 0;
for(int i = 0;i<bottom.size();i++){
for(int j = 0;j<top.size();j++){
if (find(bottom[i]) == find(top[j])){
sgn = 1;
printf("Yes\n");
break;
}
}
if (sgn)break;
}
if (!sgn)printf("No\n");
}
return 0;
}
10 搭配购买 AC
背包 + 并查集
== x’ 判断
# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
int n,m,w,v,p,u;
long long fa[10005] = {},f[10005] = {};
struct cloud{
long long value,price,id;
double ratio;
cloud(int _v,int _p,int _id){
value = _v;
price = _p;
id = _id;
ratio = double(value)/double(price);
};
cloud(){};
};
long long find(long long x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
vector<cloud>c;
bool cmp(cloud a,cloud b){
if (a.ratio > b.ratio)return a.ratio>b.ratio;
else return a.price<b.price;
}
int main(){
scanf("%d %d %d",&n,&m,&w);
for (int i = 0;i<n;i++)fa[i] = i;
for (int i = 0;i<n;i++){
scanf("%d %d",&v,&p);
c.push_back(cloud(p,v,i));
}
for (int i = 0;i<m;i++){
scanf("%d %d",&u,&v);
fa[find(v-1)] = find(u-1);
}
for(int i = 0;i<n;i++){
if(fa[i] != i){
c[find(i)].price += c[i].price;
c[find(i)].value += c[i].value;
c[i].price = 0;
c[i].value = 0;
}
}
for (int i=1;i<=n;i++)
for (int j=w;j>=c[i].price;j--)
f[j]=max(f[j],f[j-c[i].price]+c[i].value); //01背包
printf("%lld\n",f[w]);
return 0;
}
11 并查集内计数 AC
# include <cstdio>
int fa[2][10005] = {},n,m,p,q,a,b;
int find(int x,int typ){
if (fa[typ][x] == x)return x;
else return fa[typ][x] = find(fa[typ][x],typ);
}
void merge(int a,int b,int typ){
if (find(a,typ) != find(b,typ))
fa[typ][find(a,typ)] = find(b,typ);
}
int main(){
scanf("%d %d %d %d",&n,&m,&p,&q);
for(int i = 0;i<=n;i++)fa[0][i] = i;
for(int i = 0;i<=m;i++)fa[1][i] = i;
for(;p;p--)scanf("%d %d",&a,&b),merge(a,b,0);
for(;q;q--)scanf("%d %d",&a,&b),merge(-a,-b,1);
int ca = 0,cb = 0;
for(int i = 0;i<=n;i++)
if (find(i,0) == find(1,0))ca ++;
for(int i = 0;i<=m;i++)
if (find(i,1) == find(1,1))cb ++;
printf("%d",ca>cb?cb:ca);
return 0;
}
12 统计并查集的数 AC
用 set.size() 统计不同 father 的个数
# include <cstdio>
# include <set>
using namespace std;
int fa[1005] = {},m,n,a,b;
int find(int x){
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void merge(int a,int b){
if (find(a) != find(b))
fa[find(a)] = find(b);
}
int main(){
while(scanf("%d",&n) && n){
scanf("%d",&m);
for(int i = 0;i<=n;i++)fa[i] = i;
for(;m;m--){
scanf("%d %d",&a,&b);
merge(a,b);
}
set<int>st;
for(;n;n--)st.insert(find(n));
printf("%d\n",(int)st.size()-1);
}
return 0;
}
13 运动会 AC
map + 并查集
# include <cstdio>
# include <string>
# include <iostream>
# include <map>
using namespace std;
int fa[20005] = {},m,n,k,a,b;
string s1,s2;
map<string,int>ma;
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
void merge(int a,int b){
if (find(a) != find(b))
fa[find(a)] = find(b);
}
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
for (int i = 0;i<=n;i++)fa[i] = i;
for(int i = 0;i<n;i++){
cin>>s1;
ma.insert(make_pair(s1, i));
}
for(int i = 0;i<m;i++){
cin>>s1>>s2;
merge(ma[s1],ma[s2]);
}
cin>>k;
for(;k;k--){
cin>>s1>>s2;
if (find(ma[s1]) == find(ma[s2])) cout<<"Yes.\n";
else cout<<"No.\n";
}
return 0;
}
而大佬的方法，直接把 fa[] 改成 string 到 string 的 map
#include<iostream>
#include<cstdio>
#include<map>//map库
using namespace std;
map<string,string> a;//建立映射
string fin(string x){//查找字符串x的祖先
if(a[x]==x) return x;
else return a[x]=fin(a[x]);//路径压缩
}
int main(){
int n,m,k;
string s1,s2;//s1,s2可重复使用
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>s1;//选手名字
a[s1]=s1;//每个人的祖先初始化为自己
}
for(int i=1;i<=m;++i){
cin>>s1>>s2;//两位选手
string x1=fin(s1),x2=fin(s2);//合并
if(x1!=x2) a[x1]=x2;
}
cin>>k;
for(int i=1;i<=k;++i){
cin>>s1>>s2;
string x1=fin(s1),x2=fin(s2);//查询
if(x1!=x2) printf("No.\n");
else printf("Yes.\n");
}
return 0;//后话：STL大法好！
}
14 最小生成树 AC
kruscarl 并查集实现
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int fa[5010] = {};
int n,m,f,t,e;
struct edge{
int from,to,length;
edge(int f,int t,int e):from(f),to(t),length(e){}
};
bool cmp(edge a,edge b){
return a.length < b.length;
}
vector<edge>lst;
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<=n;i++)fa[i] = i;
for(int i = 0;i<m;i++){
scanf("%d %d %d",&f,&t,&e);
lst.push_back(edge(f,t,e));
}
sort(lst.begin(), lst.end(), cmp);
int res = 0;
for(int i = 0,j = 0;i<n-1;j++){
if (j == m){
printf("orz");
return 0;
}
// printf("%d %d %d %d\n",lst[j].from,lst[j].to,find(lst[j].from),find(lst[j].to));
if (find(lst[j].from) != find(lst[j].to)){
res += lst[j].length;
fa[find(lst[j].from)] = find(lst[j].to);
i++;
}
}
printf("%d",res);
return 0;
}
15 无线通信网 AC
kruscal 控制最后有 p-s+1 个联通区块
# include <cstdio>
# include <vector>
# include <cmath>
# include <algorithm>
using namespace std;
int fa[250005] = {};
int s,p,x,y;
struct edge{
int from,to;
double length;
edge(int f,int t,double e):from(f),to(t),length(e){}
};
struct node{
int x,y;
node(int _x,int _y):x(_x),y(_y){}
};
bool cmp(edge a,edge b){
return a.length < b.length;
}
double cal(node a,int x,int y){
return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
}
vector<edge>elst;
vector<node>nlst;
int find(int x){
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
int main(){
scanf("%d %d",&s,&p);
for(int i = 0;i<p;i++){
scanf("%d %d",&x,&y);
for(int j = 0;j<nlst.size();j++){
elst.push_back(edge(i,j,cal(nlst[j],x,y)));
}
nlst.push_back(node(x,y));
}
sort(elst.begin(),elst.end(),cmp);
for(int i = 0;i<p+1;i++)fa[i] = i;
double res = 0.0;
for(int i = 0,j = 0;i<p-s;j++){
if (find(elst[j].from) != find(elst[j].to)){
fa[find(elst[j].from)] = find(elst[j].to);
i++;
res = elst[j].length;
}
}
printf("%.02lf",res);
return 0;
}
16 家谱 AC
不能用 insert，因为 key 不能重复！
# include <cstdio>
# include <map>
# include <string>
# include <iostream>
using namespace std;
map<string,string>fa;
char sgn;
string f,s;
int main(){
while(scanf("%c",&sgn) && sgn != '$'){
if (sgn == '#') {
cin>>f;
// map 里面没有，才加入
// if (fa.find(f) == fa.end()) fa.insert(make_pair(f, f));
if (fa[f] == "") fa[f] = f;
}
else if(sgn == '+'){
cin>>s;
// fa.insert(make_pair(s, f));
fa[s] = f;
}
else if(sgn == '?'){
cin>>s;
cout<<s<<' ';
while(fa[s] != s)s = fa[s];
cout<<s<<endl;
}
}
return 0;
}
17 刻录光盘 AC
并查集是双向的，但此题为单向
不管那些特殊点（比如同一个 cluster 里面，可能有多个源点），用一个数组存一下每一个点有没有直系的父亲,其他的跟并查集没啥区别。最后 O(n) 扫一遍的时候加以判断，如果是没有直系父亲的，直接加一，其他的如果是祖先也加一。
# include <cstdio>
# include <vector>
# include <set>
using namespace std;
int fa[205] = {},havefa[205] = {};
int n,a;
int find(int x){
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++) fa[i] = i;
for(int i = 1;i<=n;i++){
while(scanf("%d",&a) && a){
havefa[a] = 1;
if (find(a) != find(i))
fa[find(a)] = find(i);
}
}
// for(int i = 1;i<=n;i++)printf("%d ",havefa[i]);
// printf("\n");
// for(int i = 1;i<=n;i++)printf("%d ",fa[i]);
// printf("\n");
int count = 0;
for(int i = 1;i<=n;i++)
if (!havefa[i] || fa[i] == i) count++;
printf("%d",count);
return 0;
}
//
//9
//6 4 0
//8 5 4 0
//1 5 7 0
//1 0
//1 0
//6 0
//1 8 0
//0
//0
入门综合练习
1 水 AC
注意等号！
//2020-02-24 14:33:41
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,s,a,b,ta,tb;
struct apple{
int h,f;
apple(int _h,int _f):h(_h),f(_f){}
};
bool cmp(apple a,apple b){
return a.f < b.f;
}
int main(){
scanf("%d%d%d%d",&n,&s,&a,&b);
int hmax = a+b,count = 0;
vector<apple>lst;
for(int i = 0;i<n;i++){
scanf("%d %d",&ta,&tb);
lst.push_back(apple(ta, tb));
}
sort(lst.begin(),lst.end(),cmp);
for(int i = 0;i<n;i++){
// printf("%d-%d-%d-%d\n",lst[i].h,lst[i].f,s,count);
if (lst[i].h <= hmax){
if (s >= lst[i].f){
s -= lst[i].f;
count++;
}else break;
}
}
printf("%d",count);
return 0;
}
2 ABC 三位数比例 AC
太粗心了！！一定稳重！！
// 2020-02-24 15:06:56
# include <cstdio>
# include <algorithm>
bool meet(int a,int b,int c){
if (a > 987 || a < 102 || b > 987 || b < 102 ||c > 987 || c < 102)
return false;
int sum = a * 1000000 + b * 1000 + c,now;
int hash[10] = {};
for(int i = 0;i<10;i++){
now = sum % 10;
if(hash[now] != 0)return false;
else{
hash[now] ++;
sum /= 10;
}
}
return true;
}
int getup(int a){
for(int i = 100;i <= 999;i++){
if (i%a == 0)return i;
}
return 102;
}
int main(){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int end = 987/c*a+1,start = getup(a),is = 0;
for(int i = start;i<=end;i+=a){
if (meet(i,i/a*b,i/a*c)){
printf("%d %d %d\n",i,i/a*b,i/a*c);
is = 1;
}
}
if (is == 0)printf("No!!!");
return 0;
}
3 哥德巴赫猜想 AC
由于是需要三个数字和为n，限定了3，就非常简单，无需 DFS 了
// 2020-02-24 15:39:13
# include <cstdio>
using namespace std;
int n,prime[20000] = {2,3,5,7,11,13,17,19};
bool isprime(int n){
for(int i = 0;prime[i]>0 && prime[i] < n;i++){
if (n % prime[i] == 0)return false;
}
return true;
}
void getPrime(int n){
int k = 8;
for (int i = 23;i<=n;i++){
if (isprime(i))prime[k++] = i;
}
}
void get(int n){
for(int i = 0;prime[i] != 0;i++){
for(int j = i;prime[j] != 0;j++){
for(int k = j;prime[k] != 0;k++){
if (prime[i] + prime[j] + prime[k] == n){
printf("%d %d %d",prime[i],prime[j],prime[k]);
return;
}
}
}
}
}
int main(){
scanf("%d",&n);
getPrime(n);
// for(int i = 0;prime[i] != 0;i++){
// printf("%d ",prime[i]);
// }
get(n);
return 0;
}
4 小鱼 AC
// 2020-02-25 08:53:30
# include <cstdio>
int main(){
double s,x,step = 7.0,now = 0.0;
int p = 0;
scanf("%lf %lf",&s,&x);
for(int i = 0;;i++){
if (now >= s-x && now <= s+x)p++;
if (now >= s+x)break;
now += step;step *= 0.98; // 先检查！否则还没走就被发现的检查不出来了
}
if (p>=2) printf("y");
else printf("n");
return 0;
}
5 记忆化搜索 AC
# include <cstdio>
# define LL long long
# define maxn 30
int n[maxn][maxn][maxn] = {};
int w(int a,int b,int c){
if (a <= 0 || b <= 0 || c <= 0)
// return n[a][b][c] = 1; 一开始这样写，越界了！！
return 1;
else if (a > 20 || b > 20 || c > 20)
return n[20][20][20] = w(20,20,20);
else if (n[a][b][c] != 0)
return n[a][b][c];
else if (a < b && b < c)
return n[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
else
return n[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);
}
int main(){
LL a,b,c;
while(1){
int res;
scanf("%lld %lld %lld",&a,&b,&c);
if (a == -1 && b == -1 && c == -1)return 0;
res = w((int)a,(int)b,(int)c);
printf("w(%lld, %lld, %lld) = %d\n",a,b,c,res);
}
return 0;
}
6 枚举
# include <cstdio>
int main(){
int n;
scanf("%d",&n);
int i = 1,sum = 0,lastsum = 0;
for(;sum<n;i++){
lastsum = sum;
sum += i;
}
if (i%2 == 0) printf("%d/%d",i-n+lastsum,n-lastsum);
else printf("%d/%d",n-lastsum,i-n+lastsum);
return 0;
}
7 解方程 AC
注意 -0.000 问题，以及每一个 num 都必须 * isnegative * isinverted
# include <cstdio>
# include <cstring>
int a = 0,b = 0,isnegative = 1,isinverted = 1,end = 1;
// isnegative 是负数 isinverted 在等号右边 end 结束
char variable;
void input(){
int num = 0;
char c = getchar();
// printf("char = %c--\n",c);
while(c >= '0' && c <= '9'){
num *= 10;
num += int(c-'0');
c = getchar();
}
// printf("num = %d\n",num);
if (c >= 'a' && c <= 'z') {
if (num != 0)a += (isnegative * num * isinverted);
else a += isnegative * isinverted;
variable = c;
}
else {
b += (isnegative * isinverted * num);
if (c == '-')isnegative = -1;
else if (c == '+')isnegative = 1;
else if (c == '='){
isinverted = -1;
isnegative = 1; //一定别忘了回归正号！
}
else end = 0;
}
// printf("%d %d---\n",a,b);
}
int main(){
while(end){
input();
}
double res = -double(b)/(double)a;
if (b != 0 && !(res<0.001 && res>-0.001))
printf("%c=%.03lf",variable,res);
else printf("%c=%.03lf",variable,0.000); // 第5点：常数为零
return 0;
}
高精度
全都直接用 python！
1 高精度 + – x: 1601 2142 1303
题解过于简单，略
2 数楼梯 AC
注意修改系统递归深度！同时 return b[n] = sth 在 python 是不正确的语法！
import sys
sys.setrecursionlimit(100000) # 修改最大递归深度，否则报错
a = int(input())
b = [0]*5001
b[0] = 0;b[1] = 1;b[2] = 2
def getsolution(n):
if b[n] == 0:
b[n] = getsolution(n-1) + getsolution(n-2)
return b[n]
if a>0:
print(getsolution(a))
else:
print(0)
然而，一个大佬题解让人刮目相看：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数
void hp(int k)//高精度加法，k来存阶数
{
int i;
for(i=1;i<=len;i++)
f[k][i]=f[k-1][i]+f[k-2][i];//套用公式
for(i=1;i<=len;i++) //进位
if(f[k][i]>=10)
{
f[k][i+1]+=f[k][i]/10;
f[k][i]=f[k][i]%10;
if(f[k][len+1])len++;
}
}
int main()
{
int i;
scanf("%d",&n);
f[1][1]=1; f[2][1]=2; //初始化
for(i=3;i<=n;i++) //从3开始避免越界
hp(i);
for(i=len;i>=1;i--) //逆序输出
printf("%d",f[n][i]);
return 0;
}
由于输入是 int 范围，故不需要用字符串，高精用 f[][i] 也能表示！！
3 阶乘 AC
# https://www.luogu.com.cn/problem/P1591
import re
n = int(input())
for i in range(n):
m = [int(i) for i in input().split(' ')]
res = 1
for j in range(1,m[0]+1):
res = res * j
r = str(res)
p = re.findall(str(m[1]),r)
print(len(p))
4 B进制星球 AC
其他进制加法，直接字符算
# include <map>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
char hashtable[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
map<char,int>mp;
int b;
char x[2001],y[2001],z[2005];
int pluss(char x,char y,int sgn){
return mp[x]+mp[y]+sgn;
}
int main(){
for(int i = 0;i<37;i++) mp[hashtable[i]] = i;
scanf("%d",&b);
scanf("%s %s",x,y);
reverse(x, x+strlen(x));
reverse(y, y+strlen(y));
int sgn = 0;
if (strlen(x) < strlen(y)){
for(int i = strlen(x);i<=strlen(y);i++)x[i] = '0';
y[strlen(y)] = '0';
}else{
for(int i = strlen(y);i<=strlen(x);i++)y[i] = '0';
x[strlen(x)] = '0';
}
for(int i = 0;i<strlen(x) && i < strlen(y);i++){
int t = pluss(x[i],y[i],sgn);
if (i == strlen(x)-1 && t == 0)break;
if (t >= b){
z[i] = hashtable[t-b];
sgn = 1;
}else{
z[i] = hashtable[t];
sgn = 0;
}
}
reverse(z, z+strlen(z));
printf("%s",z);
}
数学问题
1 next_permutation AC
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,p,t;
int main(){
// printf("fas");
// return 0;
scanf("%d%d",&n,&p);
vector<int>a;
for(int i = 0;i<n;i++){
scanf("%d",&t);
a.push_back(t);
}
for(int i = 0;i<p;i++){
next_permutation(a.begin(), a.end());
}
for(int i = 0;i<n;i++){
printf("%d",a[i]);
if (i < n-1) printf(" ");
}
return 0;
}
2 高精 AC
10**500 会超时！
import math
a = int(input())
res = 1
b=pow(2,a,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
print(int(a * math.log(2,10))+1)
r = str("%0500d" % (b-1))
for i in range(10):
print(r[i*50:(i+1)*50])
3 枚举 AC
虽然是两个数字枚举，但是不需要枚举两层，一层即可
// https://www.luogu.com.cn/problem/P1147
# include <cstdio>
# include <cmath>
# include <algorithm>
# include <vector>
using namespace std;
int m;
struct node{
int x, y;
node(int _x,int _y):x(_x),y(_y){}
};
bool cmp(node a,node b){return a.x < b.x;}
vector <node>res;
int main(){
scanf("%d",&m);
for(int i = 1;i<=m;i++){
if (m*2%i == 0 && (m*2/i)%2 == 1){
int j = m*2/i;
res.push_back(node(abs(i-j)/2+1,(i+j)/2));
}
}
sort(res.begin(), res.end(), cmp);
for (int i =0 ;i<res.size();i++){
printf("%d %d\n",res[i].x,res[i].y);
}
return 0;
}
4 分解质因数 AC
#include<bits/stdc++.h>
using namespace std;
int x,y,p,ans=1,a;
int main()
{
cin>>x>>y;
if(y%x!=0)cout<<0;
else
{
p=y/x;
a=2;
while(p!=1)
{
while(p%a!=0)a++;
while(p%a==0)p/=a;
a++;ans*=2;
}
cout<<ans;
}
return 0;
}
5 next_permutation AC
# include <cstdio>
# include <algorithm>
using namespace std;
int n,a[10] = {};
void print(){
for(int i = 1;i<=n;i++)printf("%5d",a[i]);
printf("\n");
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++)a[i] = i;
do{
print();
}while(next_permutation(a+1, a+n+1));
return 0;
}
6 约数研究 AC
# include <cstdio>
int n;
int main(){
scanf("%d",&n);
int res = 0;
for(int i = 1;i<=n;i++){
res += n/i;
}
printf("%d",res);
}
排序
1 unique AC
unique 返回 n 为前面不重复的最后位置
// 2020-02-27 09:28:33
# include <cstdio>
# include <algorithm>
using namespace std;
int n,num[10000] = {};
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&num[i]);
}
sort(num,num+n);
int p = unique(num,num+n)-num;
printf("%d\n",p);
for(int i = 0;i<p;i++){
printf("%d",num[i]);
if (i <n-1)printf(" ");
}
return 0;
}
2 分数线划定 AC
检查的时候优先检查数组下标！
# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
struct s{
int id,score;
s (int _a,int _b):id(_a),score(_b){}
};
int n,m,a,b;
vector<s>lst;
bool cmp(s a,s b){
if (a.score != b.score)return a.score > b.score;
else return a.id < b.id;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
scanf("%d %d",&a,&b);
lst.push_back(s(a,b));
}
sort(lst.begin(),lst.end(),cmp);
int finalscore = lst[int(m*1.5)-1].score,i = m*1.5-1;
for(;i<n;i++){
if (lst[i].score < finalscore)break;
}
printf("%d %d\n",finalscore,i);
for(int k = 0;k<i;k++){
printf("%d %d\n",lst[k].id,lst[k].score);
}
return 0;
}
3 高精比较大小 AC
n = int(input())
now = -1;maxn = -1;pos = -1
for i in range(n):
now = int(input())
if now > maxn:
maxn = now
pos = i
print(str(pos+1) + '\n' + str(maxn))
4 结构排序 AC
这道题真坑，“序号” 和 “编号” 是不同的，要排序两次。好好读题！
# include <cstdio>
# include <algorithm>
using namespace std;
int n,k,e[10],p;
struct m{
int id,v,x;
m(){}
m(int _id,int _v):id(_id),v(_v),x(0){}
}lst[20002];
bool cmp(m a,m b){
if (a.v != b.v)return a.v > b.v;
else return a.id < b.id;
}
int main(){
scanf("%d %d",&n,&k);
for(int i = 1;i<=10;i++) scanf("%d",&e[i%10]);
for(int i = 1;i<=n;i++){
scanf("%d",&p);
lst[i] = m(i,p);
}
sort(lst+1,lst+n+1,cmp);
for(int i = 1;i<=n;i++){
lst[i].x = i;
lst[i].v += e[i%10];
}
sort(lst+1,lst+n+1,cmp);
for(int i = 1;i<=k;i++){
printf("%d",lst[i].id);
if (i < k)printf(" ");
}
return 0;
}
5 结构体归并排序 AC
放到两个组，然后归并，只需要 O(n)
// https://www.luogu.com.cn/problem/P1309
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,r,q,temp;
struct man{
int id,s,w;
man(int _id,int _s):id(_id),s(_s),w(0){}
};
vector<man>l;
bool cmp(man a,man b){
if (a.s != b.s)return a.s > b.s;
else return a.id < b.id;
}
void merge(vector<man>a,vector<man>b){
int i = 0,j = 0;
for(int p = 0;p<2*n;p++){
// printf("%d %d %d\n",p,i,j);
if (cmp(a[i],b[j])){
l[p] = a[i++];
}else{
l[p] = b[j++];
}
if (i == n){
for(;j<n;j++)l[++p] = b[j];
break;
}else if (j == n){
for(;i<n;i++)l[++p] = a[i];
break;
}
}
}
int main(){
scanf("%d %d %d",&n,&r,&q);
for(int i = 0;i<2 * n;i++){
scanf("%d",&temp);
l.push_back(man(i+1,temp));
}
for(int i = 0;i<2 * n;i++){
scanf("%d",&temp);
l[i].w = temp;
}
sort(l.begin(), l.end(), cmp);
for(int ii = 0;ii<r;ii++){
vector<man>a; // 赢家进入 a，输进入 b
vector<man>b;
for(int i = 0;i<n;i++){
if (l[i*2].w > l[2*i + 1].w){
l[i*2].s++;
a.push_back(l[i*2]);
b.push_back(l[i*2+1]);
}else{
l[i*2+1].s++;
b.push_back(l[i*2]);
a.push_back(l[i*2+1]);
}
}
// for(int i = 0;i<n;i++) printf("%d-%d ",a[i].id,a[i].s);
// printf("\n");
// for(int i = 0;i<n;i++) printf("%d-%d ",b[i].id,b[i].s);
// printf("\n");
merge(a,b); // AB 合并
// sort(l.begin(), l.end(), cmp); // 超时
// for(int i = 0;i<n*2;i++) printf("%d-%d ",l[i].id,l[i].s);
// printf("\n");
}
printf("%d",l[q-1].id);
return 0;
}
6 水题 AC
# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
int getscore(int q,int p,int g,int x,int l){
int sum = 0;
if (q > 80 && l > 0)sum +=8000;
if (q > 85 && p > 80)sum += 4000;
if (q > 90)sum += 2000;
if (x && q > 85)sum += 1000;
if (p > 80 && g)sum += 850;
return sum;
}
int n,maxmoney = 0,totalmoney = 0;
char na[21],finalna[21],g,x;
int q,p,l;
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%s %d %d %c %c %d",na,&q,&p,&g,&x,&l);
int temp = getscore(q,p,g=='Y'?1:0,x=='Y'?1:0,l);
totalmoney += temp;
if (temp > maxmoney){
maxmoney = temp;
for(int i = 0;i<strlen(na);i++){
finalna[i] = na[i];
}finalna[strlen(na)] = '\0';
}
}
printf("%s\n%d\n%d",finalna,maxmoney,totalmoney);
return 0;
}
7 水题 AC
# include <cstdio>
# include <algorithm>
using namespace std;
struct stu{
int ch,all,id;
stu(){};
stu(int _a,int _b,int _c):id(_a),ch(_b),all(_c){}
}s[301];
bool cmp(stu a,stu b){
if (a.all != b.all)return a.all > b.all;
else if (a.ch != b.ch)return a.ch > b.ch;
else return a.id < b.id;
}
int main(){
int n,a,b,c;
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d %d %d",&a,&b,&c);
s[i] = stu(i,a,a+b+c);
}
sort(s+1,s+n+1,cmp);
for(int i = 1;i<=5;i++){
printf("%d %d\n",s[i].id,s[i].all);
}
return 0;
}
8 水hash AC
# include <cstdio>
# include <algorithm>
using namespace std;
int n,m,p,a[1000] = {};
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<m;i++){
scanf("%d",&p);
a[p] ++;
}
int c = 0;
for(int i = 1;i<=n;i++){
for(int j = 0;j<a[i];j++){
printf("%d",i);
c++;
if (c < m)printf(" ");
}
}
}
9 第k小 AC
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[5000010];
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
nth_element(a,a+k,a+n);//使第k小整数就位
printf("%d",a[k]);//调用第k小整数
}
10 水 AC
# include<cstdio>
# include<algorithm>
using namespace std;
int n,b,a[20002] = {};
bool cmp(int a,int b){return a>b;}
int main(){
scanf("%d %d",&n,&b);
for(int i = 0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n,cmp);
int now = 0,i = 0;
for(;i<n;i++){
now += a[i];
if (now > b)break;
}
printf("%d",i+1);
return 0;
}
11 水 结构体排序 AC
# include <cstdio>
# include <algorithm>
# include <cmath>
using namespace std;
int n,a,b,c;
double sum = 0.0;
struct node{
int x,y,z;
node(){};
node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
}lst[50001];
bool cmp(node a,node b){
return a.z < b.z;
}
double dis(node a,node b){
return (sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2)+pow((a.z-b.z),2)));
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d %d %d",&a,&b,&c);
lst[i] = node(a,b,c);
}
sort(lst,lst+n,cmp);
double res = 0;
for(int i = 1;i<n;i++){
res += dis(lst[i],lst[i-1]);
}
printf("%.03lf",res);
return 0;
}
图
1 DJ WA
明明跟模板都一样。。
# include <cstdio>
# include <algorithm>
# include <stack>
# define MAXN 0x7fffffff
# define _rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
using namespace std;
int n,G[10][10],dis[10],vis[10] = {},pre[10] = {};
void Dj(int start){
fill(dis,dis+n,MAXN);
dis[start] = 0;
_rep(ii,0,n){
int MIN = MAXN,k = -1;
_rep(i, 0, n){
if (dis[i] < MIN && vis[i] == 0){
MIN = dis[i];
k = i;
}
}
if (k == -1)return;vis[k] = 1;
_rep(i, 0, n){
if (vis[i] == 0 && dis[i] > dis[k] + G[k][i]){
dis[i] = dis[k] + G[k][i];
pre[i] = k;
}
}
}
}
int main(){
scanf("%d",&n);
_rep(i,0,n){
_rep(j,0,n){
scanf("%d",&G[i][j]);
}
}
Dj(0);
printf("%d\n",dis[n-1]);
int now = n-1;
stack<int>st;
_rep(i, 0, n){
if (now == 0)break;
st.push(now);
now = pre[now];
}
// _rep(i, 0, n){printf("%d-",pre[i]);}
printf("1");
while(!st.empty()){
printf(" %d",st.top()+1);
st.pop();
}
return 0;
}
2 求最小环 70
我的 70 分方法（三个点 TLE）：从有出入度的点开始，挨个遍历 TODO
# include <cstdio>
const int maxn = 200000;
int n,next[maxn] = {},prev[maxn] = {};
int getcircle(int x,int n){
int i = x,count = 1;
int vis[maxn] = {};
while(next[i] != x && !vis[i]){
count ++;
if (count>=n)break;
vis[i] ++;
i = next[i];
}
return count;
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&next[i]);
prev[next[i]] = 1;
}
int min = n;
for(int i = 1;i<=n;i++){
if(prev[i] && next[i]){
int p = getcircle(i,n);
min = min<p?min:p;
if(min == 2)break;
}else{ // 如果 i 点入度为零，则把从 i 出发的边也删去
prev[next[i]] = 0;
}
}
printf("%d",min);
return 0;
}
3 二分图染色 40
TODO 真的看不懂题解
# include <cstdio>
# include <vector>
using namespace std;
int f[20001],n,m,ta,tb;
int find(int x){
if (f[x] == x)return x;
return f[x] = find(f[x]);
}
void merge(int a,int b){
f[find(a)] = find(b);
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=2 * n;i++)f[i] = i;
for(int i = 0;i<m;i++){
scanf("%d %d",&ta,&tb);
if (find(ta) == find(tb) || find(ta + n) == find(tb + n)){
printf("Impossible");
return 0;
}else{
// 种类并查集 分成两类
merge(ta, tb+n);
merge(ta+n, tb);
}
}
int count = 0;
for(int i = 1;i<=n;i++){
if (f[i] > n)count ++;
}
printf("%d",count>(n-count)?(n-count):count);
return 0;
}
4 最大父亲 AC
从大到小，反向遍历，能遍历到的就是自己作为父亲的
# include <cstdio>
# include <vector>
using namespace std;
int n,m,a,b,fa[100005],now = 0;
vector<int>g[100005];
void find(int x){
if (fa[x])return;
fa[x] = now;
for(int i = 0;i<g[x].size();i++){
find(g[x][i]);
}
}
int main(){
scanf("%d %d",&n,&m);
for(;m;m--){
scanf("%d %d",&a,&b);
g[b].push_back(a);
}
for(int i = n;i>0;i--){
now = i;
find(i);
}
for(int i = 1;i<=n;i++){
printf("%d",fa[i]);
if (i < n)printf(" ");
}
return 0;
}
5 BFS + DFS AC
# include <cstdio>
# include <vector>
# include <queue>
# include <algorithm>
using namespace std;
const int maxn = 100002;
int n,m,a,b,vis[maxn],countn = 0;
vector<int>g[maxn];
void init(){
for(int i = 0;i<=n;i++)vis[i] = 0;
countn = 0;
}
void DFS(int start){
countn++;
printf("%d ",start);
vis[start] = 1;
// if (countn < n) printf(" ");
// else printf("\n");
for(int i = 0;i<g[start].size();i++){
if (!vis[g[start][i]])DFS(g[start][i]);
}
}
void BFS(int x){
queue<int>q;
q.push(x);
vis[x] = 1;
while(!q.empty()){
int f = q.front();
q.pop();
countn ++;
printf("%d ",f);
// if (countn < n) printf(" ");
// else printf("\n");
for(int i = 0;i<g[f].size();i++){
if (!vis[g[f][i]]) {
q.push(g[f][i]);
vis[g[f][i]] = 1;
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(;m;m--){
scanf("%d %d",&a,&b);
g[a].push_back(b);
}
for(int i = 1;i<=n;i++){
sort(g[i].begin(),g[i].end());
}
DFS(1);
init();
printf("\n");
BFS(1);
return 0;
}
6 食物链 TODO
# include <cstdio>
# include <vector>
using namespace std;
# define maxn 5005
int isbegin[maxn] = {},isend[maxn] = {},vis[maxn] = {},c[maxn][maxn] = {},n,m,a,b,countn = 0;
vector<int>g[maxn],hashbegin,hashend;
int DFS(int start,int end){
if (c[start][end]) return c[start][end];
int res = 0;
if (start == end) {res = 1;}
else{
for(int i = 0;i<g[start].size();i++){
if (!vis[g[start][i]]){
vis[g[start][i]] = 1;
res += DFS(g[start][i],end);
vis[g[start][i]] = 0;
}
}
}
res %= 80112002;
c[start][end] = res;
return res;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++){
isbegin[i] = 1;
isend[i] = 1;
}
for(;m;m--){
scanf("%d %d",&a,&b);
isbegin[a] = 0;
isend[b] = 0;
g[b].push_back(a);
}
for(int i = 1;i<=n;i++)if(isbegin[i])hashbegin.push_back(i);
for(int i = 1;i<=n;i++)if(isend[i])hashend.push_back(i);
for(int i = 0;i<hashbegin.size();i++){
for(int j = 0;j<hashend.size();j++){
for(int i = 0;i<=n;i++)vis[i] = 0;
countn += DFS(hashbegin[i],hashend[j]);
}
}
printf("%d",countn%80112002);
return 0;
}
7 围棋 AC
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int g[102][102] = {},ori[102][102] = {};
int n;
char c;
void DFS(int x,int y,int color){
for(int i = 0;i<4;i++){
int nx = x+dir[i][0], ny = y + dir[i][1];
if (nx >=0 && ny >= 0 && nx <n && ny < n && g[nx][ny] == 0)
{g[nx][ny] = color;DFS(nx,ny,color);}
}
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%*c");
for(int j = 0;j<n;j++){
scanf("%c",&c);
if (c == 'B'){g[i][j] = 2;ori[i][j] = 1;}
else if (c == 'W'){g[i][j] = 1;ori[i][j] = 1;}
}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if (ori[i][j])DFS(i,j,g[i][j]);
}
}
// for(int i = 0;i<n;i++){
// for(int j = 0;j<n;j++){
// printf("%d",g[i][j]);
// }printf("\n");
// }
int count = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if (g[i][j] == 2)count ++;
}
}
printf("%d %d",count,n*n-count);
return 0;
}
8 DFS AC
# include <cstdio>
int g[101][101] = {},vis[101][101] = {};
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n,m,k,x,y,tempsum = 0,maxsum = 0;
void DFS(int x,int y){
vis[x][y] = 1;
for(int i = 0;i<4;i++){
int nx = x + dir[i][0],ny = y + dir[i][1];
if (nx > 0 && ny > 0 && nx <= n && ny <= m && vis[nx][ny] == 0 && g[nx][ny] == 1){
tempsum ++;
DFS(nx,ny);
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i = 0;i<k;i++){
scanf("%d %d",&x,&y);
g[x][y] = 1;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if (g[i][j] == 1 && vis[i][j] == 0){
tempsum = 1;
DFS(i,j);
maxsum = maxsum>tempsum?maxsum:tempsum;
}
}
}
printf("%d",maxsum);
return 0;
}
9 拓扑排序 WA TODO
# include <cstdio>
# include <vector>
using namespace std;
const int maxn = 50005;
vector<int>fa[maxn];
int w[maxn] = {},res[maxn] = {},maxres[maxn] = {},r = 0;
int n,temp;
void DFS(int x){
for(int i = 0;i<fa[x].size();i++){
res[fa[x][i]] += res[x];
if (res[fa[x][i]] > maxres[fa[x][i]]){
maxres[fa[x][i]] = res[fa[x][i]];
DFS(fa[x][i]);
}
res[fa[x][i]] -= res[x];
}
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&temp);
scanf("%d",&w[i]);
res[i] = w[i];
maxres[i] = w[i];
scanf("%d",&temp);
while(temp){
fa[i].push_back(temp);
scanf("%d",&temp);
}
}
DFS(n);
// for(int i = 1;i<=n;i++){
// printf("%d ",res[i]);
// }printf("\n");
// for(int i = 1;i<=n;i++){
// printf("%d ",maxres[i]);
// }
int maxmax = 0;
for(int i = 1;i<=n;i++){
maxmax = maxmax > maxres[i] ? maxmax : maxres[i];
}
printf("%d",maxmax);
return 0;
}
简单模拟
1 覆盖地毯 AC
从后往前，有覆盖就输出
# include <cstdio>
int n,a,b,m[10001][4];
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d %d %d %d",&m[i][0],&m[i][1],&m[i][2],&m[i][3]);
}
scanf("%d %d",&a,&b);
for(int i = n;i>0;i--){
if ((a >= m[i][0]) && (a <= m[i][0] + m[i][2]) && (b >= m[i][1]) && (b <= m[i][1] + m[i][3])){
printf("%d",i);
return 0;
}
}
printf("%d",-1);
return 0;
}
2 多项式输出 AC
分类讨论模拟
# include <cstdio>
int main(){
int n,k[101],sgn = 0;
scanf("%d",&n);
for(int i = n;i>=0;i--)scanf("%d",&k[i]);
for(int i = n;i>1;i--){
if (k[i] > 0){
if (sgn == 0){
sgn = 1;
if (k[i] == 1)printf("x^%d",i);
else printf("%dx^%d",k[i],i);
}else{
if (k[i] == 1)printf("+x^%d",i);
else printf("+%dx^%d",k[i],i);
}
}else if (k[i] < 0){
sgn = 1;
if (k[i] == -1)printf("-x^%d",i);
else printf("%dx^%d",k[i],i);
}
}
if (k[1] > 0){
if (sgn == 0){
sgn = 1;
if (k[1] == 1)printf("x");
else printf("%dx",k[1]);
}else{
if (k[1] == 1)printf("+x");
else printf("+%dx",k[1]);
}
}else if (k[1] < 0){
sgn = 1;
if (k[1] == -1)printf("-x");
else printf("%dx",k[1]);
}
if (k[0] > 0){
if (sgn == 0){
printf("%d",k[0]);
}else{
printf("+%d",k[0]);
}
}else if (k[0] < 0){
printf("%d",k[0]);
}
return 0;
}
3 FIFO 内存置换 AC
# include <cstdio>
# include <queue>
using namespace std;
int n,m,t,inmem[1005] = {};
queue<int>q;
int main(){
scanf("%d %d",&m,&n);
int count = 0;
for(int i = 0;i<n;i++){
scanf("%d",&t);
if (!inmem[t]){
count ++;
if (q.size() < m){
q.push(t);
inmem[t] = 1;
}else{
int k = q.front();
q.pop();
q.push(t);
inmem[k] = 0;
inmem[t] = 1;
}
}
}
printf("%d",count);
return 0;
}
4 排座椅 AC
# include <cstdio>
# include <algorithm>
# include <vector>
# define min(a,b) (a)>(b)?(b):(a)
using namespace std;
int m,n,k,l,d,x1,x2,y1,y2,x[1005] = {},y[1005] = {};
struct node{
int x,i;
node(int _x,int _i):x(_x),i(_i){}
};
bool cmp(node a,node b){return a.x > b.x;}
int main(){
scanf("%d %d %d %d %d",&m,&n,&k,&l,&d);
for(;d;d--){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
if (x1 == x2) y[min(y1,y2)]++;
else if (y1 == y2) x[min(x1,x2)]++;
}
vector<node>xn;
vector<node>yn;
for(int i = 0;i<n;i++){
if (x[i])xn.push_back(node(x[i],i));
if (y[i])yn.push_back(node(y[i],i));
}
sort(xn.begin(),xn.end(),cmp);
sort(yn.begin(),yn.end(),cmp);
// 最后输出还要按照 id 排序
int resx[1005],resy[1005];
for(int j = 0;j<k;j++){
resx[j] = xn[j].i;
}
for(int j = 0;j<l;j++){
resy[j] = yn[j].i;
}
sort(resx,resx+k);
sort(resy,resy+l);
for(int j = 0;j<k;j++){
printf("%d",resx[j]);
if (j < k-1) printf(" ");
}printf("\n");
for(int j = 0;j<l;j++){
printf("%d",resy[j]);
if (j < l-1) printf(" ");
}
return 0;
}
5 水模拟 AC
# include <cstdio>
int n,na,nb,a[200],b[200],resa = 0,resb = 0;
void get(int a,int b){
// printf("%d %d\n",a,b);
if ((a == 0 && b == 2)||(a == 0 && b == 3)||(a == 1 && b == 3)||(a == 2 && b == 4)||(a == 3 && b == 4)||(a == 1 && b == 0)||(a == 2 && b == 1)||(a == 3 && b == 2)||(a == 4 && b == 1)||(a == 4 && b == 0)){
resa += 1;
}else if ( a != b ){
resb ++;
}
}
int main(){
scanf("%d %d %d",&n,&na,&nb);
for (int i = 0;i<na;i++)scanf("%d",&a[i]);
for (int i = 0;i<nb;i++)scanf("%d",&b[i]);
for (int i = 0;i<n;i++){
get(a[i%na],b[i%nb]);
}
printf("%d %d",resa,resb);
return 0;
}
6 水模拟 AC
# include <cstdio>
int lr[100002],n,m,pos = 0,t,l;
char na[100002][22];
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++)scanf("%d %s",&lr[i],na[i]);
for(int i = 0;i<m;i++){
scanf("%d %d",&t,&l);
if (t == lr[pos])pos = (pos + n - l)%n;
else pos = (pos + n + l)%n;
}
printf("%s",na[pos]);
return 0;
}
7 乒乓 AC
别忘了只输入一个 E 的情况
// https://www.luogu.com.cn/problem/P1042
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
char c[70000],temp;
int w = 0,e = 0;
void end11(){
if ((w >= 11 || e >= 11) && abs(w-e) >= 2){
printf("%d:%d\n",w,e);
w = 0;
e = 0;
}
}
void end21(){
if ((w >= 21 || e >= 21) && abs(w-e) >= 2){
printf("%d:%d\n",w,e);
w = 0;
e = 0;
}
}
int main(){
int i = 0;
while(scanf("%c",&temp)){
if (temp == 'W' ||temp =='L') c[i++] = temp;
else if (temp == 'E')break;
}
// printf("%s",c);
if (strlen(c) == 0)printf("0:0\n\n0:0");
for (int i = 0;i<strlen(c);i++){
if (c[i] == 'W')w++;
else e++;
end11();
if (i == strlen(c)-1){
printf("%d:%d\n",w,e);
w = 0;
e = 0;
}
}printf("\n");
for (int i = 0;i<strlen(c);i++){
if (c[i] == 'W')w++;
else e++;
end21();
if (i == strlen(c)-1){
printf("%d:%d\n",w,e);
w = 0;
e = 0;
}
}
return 0;
}
8 扫雷 AC
# include <cstdio>
# include <cstring>
int m,n;
char in[105][106];
int get(int x,int y){
int count = 0;
if (x-1 >= 0 && y-1 >= 0 && in[x-1][y-1] == '*')count ++;
if (x-1 >= 0 && in[x-1][y] == '*')count ++;
if (x-1 >= 0 && y+1 < n && in[x-1][y+1] == '*')count ++;
if (x+1 < n && y+1 < n && in[x+1][y+1] == '*')count ++;
if (x+1 < n && in[x+1][y] == '*')count ++;
if (x+1 < n && y-1 >= 0 && in[x+1][y-1] == '*')count ++;
if (y+1 < n && in[x][y+1] == '*')count ++;
if (y-1 < n && in[x][y-1] == '*')count ++;
return count;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
scanf("%*c");
for(int j = 0;j<m;j++){
scanf("%c",&in[i][j]);
}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if (in[i][j] != '*')printf("%d",get(i,j));
else printf("*");
}
printf("\n");
}
return 0;
}
9 高精阶乘 AC
#2020-03-12 08:52:28
n = int(input())
res = 0
for i in range(1,n+1):
now = 1
for j in range(1,i+1):
now = now*j
res += now
# print(now)
print(res)
10 旋转 WA TODO
# include <cstdio>
int a[505][505] = {},n,m,x,y,r,z;
int main(){
scanf("%d %d",&n,&m);
int count = 1;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
a[i][j] = count ++;
for(;m;m--){
int temp[505][505] = {};
scanf("%d %d %d %d",&x,&y,&r,&z);
// printf("%d-%d-%d-%d\n",x,y,r,z);
if (z == 0){
for(int i = 0;i<=r*2;i++){
for(int j = 0;j<=r*2;j++){
temp[j+x-r][x+r-i] = a[i+x-r][j+x-r];}}}
else{
for(int i = 0;i<=r*2;i++){
for(int j = 0;j<=r*2;j++){
temp[x+r-j][i+x-r] = a[i+x-r][j+x-r];}}}
for(int i = 0;i<=r*2;i++){
for(int j = 0;j<=r*2;j++){
a[i+x-r][j+x-r] = temp[i+x-r][j+x-r];}}
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
printf("%d",a[i][j]);
if (j < n)printf(" ");
}
printf("\n");
}
return 0;
}
11 找牛模拟 AC
// # 2020-03-13 08:32:40
# include <cstdio>
# include <cstring>
char g[11][11];
int cx,cy,fx,fy,countc = 0,countf = 0,count = 0;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}},v[21][21][4][21][21][4] = {};
int main(){
for(int i = 0;i<10;i++){
// Windows换行符是两个，因此要用 %s 输入，避免麻烦
scanf("%s",g[i]);
for(int j = 0;j<10;j++){
if (g[i][j] == 'C') {
cx = i;
cy = j;
}
if (g[i][j] == 'F') {
fx = i;
fy = j;
}
}
// scanf("%*c");
}
int sgn = 0;
while(1){
// printf("((%d-%d)(%d-%d))",cx,cy,fx,fy);
count ++;
if (v[cx][cy][countc][fx][fy][countf] == 1){
printf("%d",0);
return 0;
}
v[cx][cy][countc][fx][fy][countf] ++;
int ccx = cx + dir[countc][0],ccy = cy + dir[countc][1],ffx = fx + dir[countf][0],ffy = fy + dir[countf][1];
if (ccx >= 0 && ccx < 10 && ccy >= 0 && ccy < 10 && g[ccx][ccy] != '*'){
cx = ccx;
cy = ccy;
sgn++;
}else countc = (countc+1)%4;
if (ffx >= 0 && ffx < 10 && ffy >= 0 && ffy < 10 && g[ffx][ffy] != '*'){
fx = ffx;
fy = ffy;
sgn++;
}else countf = (countf+1)%4;
if (cx == fx && cy == fy){
printf("%d\n",count);
return 0;
}
// if ((g[cx][cy] == 'C' && g[fx][fy] == 'F') && sgn > 4){
// printf("%d",0);
// return 0;
// }
}
return 0;
}
12 数方块 AC
# include <cstdio>
# define LL long long
int main(){
LL n,m;
scanf("%lld %lld",&n,&m);
LL s = n*(n+1)*m*(m+1)/4;
LL a = m>n?m:n,b = m<n?m:n;
LL sum = 0;
for(LL i = 1;i<=b;i++){
sum += (a+1-i)*(b+1-i);
}
printf("%lld %lld",sum,s-sum);
return 0;
}
13 涂国旗 AC
# include <cstdio>
# include <cstring>
char c[50];
int n,m,a[55][3] = {};
int get(int i,int j){
int res = 0;
for(int p = 0;p<i;p++)res += a[p][0];
for(int p = i;p<j;p++)res += a[p][1];
for(int p = j;p<n;p++)res += a[p][2];
// printf("res=%d,",res);
return res;
}
int main(){
scanf("%d %d%*c",&n,&m);
for(int i = 0;i<n;i++){
scanf("%s",c);
for(int j = 0;j<m;j++){
if (c[j] != 'W')a[i][0] ++;
if (c[j] != 'B')a[i][1] ++;
if (c[j] != 'R')a[i][2] ++;
}
}
// for(int i = 0;i<n;i++)printf("%d %d %d\n",a[i][0],a[i][1],a[i][2]);
int sum = 0xffffff;
for(int i = 1;i<n-1;i++){
for(int j = i+1;j<n;j++){
int s = get(i,j);
sum = sum<s?sum:s;
}
}
printf("%d",sum);
return 0;
}
14 站队枚举 AC
# include <cstdio>
# include <cstring>
int a[105][105] = {},r,c,k,count = 0;
char ch[105];
int main(){
scanf("%d %d %d%*c",&r,&c,&k);
for(int i = 0;i<r;i++){
scanf("%s",ch);
for(int j = 0;j<c;j++){
if (ch[j] == '#') a[i][j] = 1;
}a[i][c] = 1;
}
// 外圈包围 1
for(int j = 0;j<=c;j++)a[r][j] = 1;
// for(int i = 0;i<r;i++){
// for(int j = 0;j<c;j++){
// printf("%d ",a[i][j]);
// }
// printf("\n");
// }
// 行
for (int i = 0;i<r+1;i++){
int start = -1;
for(int j = 0;j<c+1;j++){
if(a[i][j]){
int end = j;
int p = end - start - 1;
if(p-(k-1) > 0){
// printf("+++%d %d %d %d\n",i,start,end,p);
count += (p-(k-1));}
start = j;
}
}
// printf("%d-",count);
}
// 列
if(k != 1){ // 如果是一个人，行列就重复了
for (int i = 0;i<c+1;i++){
int start = -1;
for(int j = 0;j<r+1;j++){
if(a[j][i]){
int end = j;
int p = end - start - 1;
if(p-(k-1) > 0){
// printf("+++%d %d %d %d\n",i,start,end,p);
count += (p-(k-1));}
start = j;
}
}
}
}
printf("%d",count);
return 0;
}
15 回文质数 AC
# include <cstdio>
# include <cmath>
# include <string>
# include <algorithm>
using namespace std;
int a,b,prime[100000000] = {2,3,5};
bool isp(int x){
for(int i = 0;prime[i] <= sqrt(x);i++){
if (x%prime[i] == 0)return false;
}
return true;
}
void get(int b){
int count = 3;
for(int i = 7;i<b;i++){
if (isp(i)) prime[count++] = i;
}
}
bool ishw(int x){
string t = to_string(x);
string u = t;
reverse(t.begin(), t.end());
return t == u;
}
int main(){
scanf("%d %d",&a,&b);
// get(b);
// for (int i = 0;prime[i] != 0;i++){
// if (prime[i] >= a && ishw(prime[i])) printf("%d,",prime[i]);
// }
int res[10000] = {5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
for(int i = 0;res[i] <= b;i++){
if (res[i] >= a)printf("%d\n",res[i]);
}
}
16 火柴棒等式 AC
# include <cstdio>
int num[10] = {6,2,5,5,4,5,6,3,7,6},n,a,b,c;
int getuse(int x){
if (x == 0)return 6;
int res = 0;
while (x != 0){
int p = x%10;
x /= 10;
res += num[p];
}
return res;
}
int main(){
scanf("%d",&n);
n-=4;
int r = 0;
for(int i = 0;i<1000;i++){
for(int j = 0;j<1000;j++){
if (getuse(i)+getuse(j)+getuse(i+j) == n){
r++;
// printf("%d+%d=%d (%d)(%d)(%d)\n",i,j,i+j,getuse(i),getuse(j),getuse(i+j));
}
}
}
printf("%d",r);
return 0;
}
17 凑等边三角形 AC
# include <cstdio>
int n,hash[5004] = {},t;
long long res = 0;
int main(){
scanf("%d",&n);
for(;n;n--){
scanf("%d",&t);
hash[t] ++;
}
for(int i = 1;i<2505;i++){
for(int j = i;i+j<5001;j++){
if (hash[i+j] > 1 && hash[i] > 0 && hash[j] > 0){
if (i != j)
res += (hash[i] * hash[j] * hash[i+j] * (hash[i+j]-1) /2);
else res += (hash[i] * (hash[j]-1) * hash[i+j] * (hash[i+j]-1) /4);
}
}
}
printf("%lld",res%(1000000007));
}
字符串处理
1 水 AC
# 2020-03-05 14:23:32
ch = input().split(" ")
num = ["","one", "two", "three", "four", "five", "six", "seven", "eight", "nine", 'ten', 'eleven', "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty"]
res = []
ii = [0]*21
def get(i):
if ii[i] != 0:
return ii[i]
else:
ii[i] = pow(i,2,100)
return ii[i]
for w in ch:
for i in range(1,21):
if num[i] == w:
res.append("%02d"%get(i))
break
elif w == 'a' or w == 'another' or w == 'first':
res.append("01")
break
elif w == 'both' or w == 'second':
res.append("04")
break
elif w == 'third':
res.append("09")
break
if len(res) == 0:
print(0)
else:
res.sort()
r = ''
for i in range(len(res)):
r += res[i]
print(int(r))
python 结构体排序：
>>> student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
2 字符串计数 + 质数判断 AC
# include <cstdio>
# include <cstring>
int hashtable[26] = {}, prime[8] = {2,3,5,7,11,13,17,19};
char c[200];
bool isprime(int res){
if (res == 1)return false;
int sgn = 1;
for(int i = 0;i<8;i++){
if (res != prime[i] && res % prime[i] == 0)sgn = 0;
}
return sgn;
}
int main(){
scanf("%s",c);
for(int i = 0;i<strlen(c);i++){
hashtable[int(c[i]-'a')]++;
}
int ma = -1,mi = 200;
for(int i = 0;i<26;i++){
if (hashtable[i] != 0){
if (ma < hashtable[i])ma = hashtable[i];
if (mi > hashtable[i])mi = hashtable[i];
}
}
int res = ma - mi;
// int res = 0;
// scanf("%d",&res);
if (isprime(res))printf("Lucky Word\n%d",res);
else printf("No Answer\n0");
return 0;
}
3 split + len AC
n = int(input())
typ = 0
cc = ""
for i in range(n):
c = input().split(" ")
if len(c) == 3:
if c[0] == 'a':
typ = 1
elif c[0] == 'b':
typ = 2
elif c[0] == 'c':
typ = 3
if (typ == 1):
cc = ("%d+%d=%d" % (int(c[1]),int(c[2]),int(c[1])+int(c[2])))
elif (typ == 2):
cc = ("%d-%d=%d" % (int(c[1]),int(c[2]),int(c[1])-int(c[2])))
elif (typ == 3):
cc = ("%d*%d=%d" % (int(c[1]),int(c[2]),int(c[1])*int(c[2])))
elif len(c) == 2:
if (typ == 1):
cc = ("%d+%d=%d" % (int(c[0]),int(c[1]),int(c[1])+int(c[0])))
elif (typ == 2):
cc = ("%d-%d=%d" % (int(c[0]),int(c[1]),int(c[0])-int(c[1])))
elif (typ == 3):
cc = ("%d*%d=%d" % (int(c[0]),int(c[1]),int(c[1])*int(c[0])))
print(cc + "\n" + str(len(cc)))
4 字符串计数 AC
import re
a = input().lower()
b = input().lower()
lb = b.split(" ")
count = 0
for i in range(len(lb)):
if a == lb[i]:
count += 1
if count > 0:
pos = lb.index(a)
index = 0
for i in range(pos):
index += len(lb[i]) + 1
print(str(count) + ' ' + str(index))
else:
print(-1)
5 反转数字 AC
# include <cstdio>
# include <cstring>
# include <string>
# include <algorithm>
using namespace std;
char c[30];
char a[30],b[30];
int typ = 0;
int get(char c[]){
int i = 0;
for(;i<strlen(c);i++){
if (c[i] == '.'){typ = 1;return i;}
if (c[i] == '/'){typ = 2;return i;}
if (c[i] == '%'){typ = 3;return i;}
a[i] = c[i];
}
return i;
}
void printa(char c[]){
int sgn = 1;
for(int i = 0;i<strlen(c);i++){
if (c[i] != '0')sgn = 0;
if (sgn == 0)printf("%c",c[i]);
}
if(sgn == 1)printf("0"); //整数部分为 0 没有考虑
}
int mzero(char c[]){
for(int i = 0;i<strlen(c);i++){
if (c[i] != '0')return i;
}
return (int)strlen(c);
}
int main(){
scanf("%s",c);
int pos = get(c);
if (typ == 0){
reverse(a, a+pos);
printa(a);
}
else if (typ == 1){
reverse(a,a+pos);
for(int i = pos+1;i<strlen(c);i++) b[i-pos-1] = c[i];
int bpos = mzero(b);
reverse(b+bpos,b+strlen(b));
// printf("%s",a);
printa(a);
printf(".");
if (bpos == strlen(b))printf("0");
else
for(int i = bpos;i<strlen(b);i++)
printf("%c",b[i]);
}
else if (typ == 2){
reverse(a,a+pos);
for(int i = pos+1;i<strlen(c);i++) b[i-pos-1] = c[i];
reverse(b,b+strlen(b));
printa(a);
printf("/");
printa(b); // 小数和分数也是不同的！
}else if (typ == 3){
reverse(a, a+pos);
printa(a);
printf("%%");
}
}
6 字符串树状图 AC
# include <cstdio>
# include <cstring>
# include <iostream>
using namespace std;
char c[105];
int hashtable[26] = {};
int main(){
for (int ii = 0;ii < 4;ii ++){
cin.getline(c,105);
// printf("%d %s\n",ii,c);
for(int i = 0;i<strlen(c);i++){
if (c[i] != ' ')hashtable[c[i] - 'A'] ++;
}
}
int maxcount = 0;
for(int i = 0;i<26;i++){
// printf("%d ",hashtable[i]);
maxcount = maxcount < hashtable[i]?hashtable[i]:maxcount;
}
for(int i = 0;i<maxcount;i++){
for(int j = 0;j<26;j++){
if (hashtable[j] < maxcount - i)printf(" ");
else printf("*");
if (j < 25)printf(" ");
}
printf("\n");
}
for(int i = 0;i<26;i++){
printf("%c",'A' + i);
if (i < 25)printf(" ");
}
}
搜索
1 暴力 AC
# include <cstdio>
int n,start[10005] = {},count = 0,vis[102][102] = {};
char a[102][102];
void DFS(int start){
int x = start/n,y = start%n;
if (x + 6 < n && y + 6 <n)
if (a[x+1][y+1] == 'i' && a[x+2][y+2] == 'z' && a[x+3][y+3] == 'h' && a[x+4][y+4] == 'o' && a[x+5][y+5] == 'n' && a[x+6][y+6] == 'g')
for (int i = 0;i<7;i++)
vis[x+i][y+i] = 1;
if (x - 6 >= 0 && y - 6 >= 0)
if (a[x-1][y-1] == 'i' && a[x-2][y-2] == 'z' && a[x-3][y-3] == 'h' && a[x-4][y-4] == 'o' && a[x-5][y-5] == 'n' && a[x-6][y-6] == 'g')
for (int i = 0;i<7;i++)
vis[x-i][y-i] = 1;
if (x - 6 >= 0 && y + 6 < n)
if (a[x-1][y+1] == 'i' && a[x-2][y+2] == 'z' && a[x-3][y+3] == 'h' && a[x-4][y+4] == 'o' && a[x-5][y+5] == 'n' && a[x-6][y+6] == 'g')
for (int i = 0;i<7;i++)
vis[x-i][y+i] = 1;
if (x + 6 < n && y - 6 >= 0)
if (a[x+1][y-1] == 'i' && a[x+2][y-2] == 'z' && a[x+3][y-3] == 'h' && a[x+4][y-4] == 'o' && a[x+5][y-5] == 'n' && a[x+6][y-6] == 'g')
for (int i = 0;i<7;i++)
vis[x+i][y-i] = 1;
if (x - 6 >= 0)
if (a[x-1][y] == 'i' && a[x-2][y] == 'z' && a[x-3][y] == 'h' && a[x-4][y] == 'o' && a[x-5][y] == 'n' && a[x-6][y] == 'g')
for (int i = 0;i<7;i++)
vis[x-i][y] = 1;
if (x + 6 < n)
if (a[x+1][y] == 'i' && a[x+2][y] == 'z' && a[x+3][y] == 'h' && a[x+4][y] == 'o' && a[x+5][y] == 'n' && a[x+6][y] == 'g')
for (int i = 0;i<7;i++)
vis[x+i][y] = 1;
if (y + 6 < n)
if (a[x][y+1] == 'i' && a[x][y+2] == 'z' && a[x][y+3] == 'h' && a[x][y+4] == 'o' && a[x][y+5] == 'n' && a[x][y+6] == 'g')
for (int i = 0;i<7;i++)
vis[x][y+i] = 1;
if (y - 6 >= 0)
if (a[x][y-1] == 'i' && a[x][y-2] == 'z' && a[x][y-3] == 'h' && a[x][y-4] == 'o' && a[x][y-5] == 'n' && a[x][y-6] == 'g')
for (int i = 0;i<7;i++)
vis[x][y-i] = 1;
}
int main(){
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%s",a[i]);
for (int j = 0;j<n;j++){
if (a[i][j] == 'y'){
start[count++] = n*i+j;
}
}
// scanf("%*c");
}
for (int i = 0;i<count;i++){
DFS(start[i]);
}
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
if (vis[i][j] == 1){
printf("%c",a[i][j]);
}else{
printf("*");
}
}
printf("\n");
}
return 0;
}
2 DFS基础 AC
DFS 步骤：
判断是否到达终点
循环「下一步」
vis++
走下一步
vis--
# include <cstdio>
int g[6][6] = {},vis[6][6] = {},count = 0;
int n,m,t,sx,sy,ex,ey,tx,ty;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void DFS(int x,int y){
if (x == 0 || y == 0 || x > n || y > m)return;
if (x == ex && y == ey){
count++;
return;
}
for (int i = 0;i<4;i++){
if (vis[x+dir[i][0]][y+dir[i][1]] == 0 && g[x+dir[i][0]][y+dir[i][1]] == 0){
vis[x][y] = 1;
DFS(x+dir[i][0],y+dir[i][1]);
vis[x][y] = 0;
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&t);
scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
for (;t;t--){
scanf("%d %d",&tx,&ty);
g[tx][ty] = 1;
}
DFS(sx, sy);
printf("%d",count);
return 0;
}
DFS 模板：
int search(int t)
{
if(满足输出条件)
{
输出解;
}
else
{
for(int i=1;i<=尝试方法数;i++)
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
search(t+1);
恢复到打标记前的状态;//也就是说的{回溯一步}
}
}
}
3 数组染色 AC
逆向思维：从四周开始，BFS 染色题目不要求的0，最后反着输出即可
BFS注意数组下标要先判断
# include <cstdio>
# include <queue>
using namespace std;
int g[51][51] = {},vis[51][51] = {};
int n;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
struct point{
int x,y;
point(int _x,int _y):x(_x),y(_y){}
};
void BFS(int x,int y){
vis[x][y] = 1;
queue<point>q;
q.push(point(x,y));
while(!q.empty()){
point top = q.front();
q.pop();
for (int i = 0;i<4;i++){
if (top.x+dir[i][0] > 0 && top.x+dir[i][0] < n && top.y+dir[i][1] > 0 && top.y+dir[i][1] < n && vis[top.x+dir[i][0]][top.y+dir[i][1]] == 0 && g[top.x+dir[i][0]][top.y+dir[i][1]] == 0){
q.push(point(top.x+dir[i][0],top.y+dir[i][1]));
vis[top.x+dir[i][0]][top.y+dir[i][1]] =1;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
scanf("%d",&g[i][j]);
}
}
for (int i = 0;i<n;i++){
if (vis[i][0] == 0 && g[i][0] == 0) BFS(i,0);
if (vis[i][n-1] == 0 && g[i][n-1] == 0) BFS(i,n-1);
if (vis[0][i] == 0 && g[0][i] == 0) BFS(0,i);
if (vis[n-1][i] == 0 && g[n-1][i] == 0) BFS(n-1,i);
}
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
if (vis[i][j] == 1) printf("0");
else if (g[i][j] == 1) printf("1");
else if (g[i][j] == 0) printf("2");
if (j < n-1)printf(" ");
else printf("\n");
}
}
return 0;
}
4 01迷宫 WA
# include <cstdio>
# include <queue>
using namespace std;
const int maxn = 1005;
// g 存迷宫，vis 存每次 BFS 的是否访问，res 存每个点的联通结果，就不用每次都 BFS 了
int g[maxn][maxn] = {}, res[maxn][maxn] = {};
int n,m,x,y;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
struct node{
int x,y;
node(int _x,int _y):x(_x),y(_y){}
};
int BFS(int x,int y){
if (res[x][y] != 0) return res[x][y];
int vis[maxn][maxn] = {};
vis[x][y] = 1;
queue<node>q;
q.push(node(x,y));
while(!q.empty()){
node top = q.front();
q.pop();
vis[top.x][top.y] = 1;
for (int i = 0;i<4;i++){
if (top.x + dir[i][0] >= 0 && top.x + dir[i][0] <n
&& top.y + dir[i][1] >= 0 && top.y + dir[i][1] <n
&& g[top.x][top.y] != g[top.x + dir[i][0]][top.y + dir[i][1]]
&& vis[top.x + dir[i][0]][top.y + dir[i][1]] == 0)
q.push(node(top.x + dir[i][0],top.y + dir[i][1]));
}
}
int count = 0;
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
if (vis[i][j] == 1) count ++;
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
if (vis[i][j] == 1) res[i][j] = count;
return count;
}
int main(){
scanf("%d %d",&n,&m);
char t;
for (int i = 0;i<n;i++){
scanf("%*c");
for (int j = 0;j<n;j++){
scanf("%c",&t);
if (t == '0')g[i][j] = 0;
else g[i][j] = 1;
}
}
for (;m;m--){
scanf("%d %d",&x,&y);
int aa = BFS(x-1,y-1);
printf("%d\n",aa);
// for(int i = 0;i<n;i++){
// printf("\n");
// for(int j = 0;j<n;j++)
// printf("%3d ",res[i][j]);
// }
// printf("\n");
}
return 0;
}
5 马的遍历 AC
带深度的 BFS
// 2020-03-07 08:12:16
# include <cstdio>
# include <queue>
using namespace std;
int x,y,a,b,g[401][401] = {};
int dir[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
struct node{
int x,y,depth;
node(int _x,int _y,int _d):x(_x),y(_y),depth(_d){}
};
int main(){
scanf("%d %d %d %d",&x,&y,&a,&b);
for (int i = 0;i<x;i++)
for(int j = 0;j<y;j++)
g[i][j] = -1;
int step = 0;
g[a-1][b-1] = 0;
queue<node>q;
q.push(node(a-1,b-1,0));
while(!q.empty()){
int topx = q.front().x,topy = q.front().y,d = q.front().depth;
q.pop();
step = d+1;
for (int i = 0;i<8;i++){
if (topx+dir[i][0] < x && topx+dir[i][0] >= 0 &&
topy+dir[i][1] < y && topy+dir[i][1] >= 0 &&
g[topx+dir[i][0]][topy+dir[i][1]] == -1){
g[topx+dir[i][0]][topy+dir[i][1]] = step;
q.push(node(topx+dir[i][0],topy+dir[i][1],step));
}
}
}
for(int i = 0;i<x;i++){
for(int j = 0;j<y;j++){
printf("%-5d",g[i][j]);
}
printf("\n");
}
return 0;
}
6 数字三角 AC
# include <cstdio>
# include <algorithm>
using namespace std;
int n,ssum,a[15][15] = {1,1,1,1,1};
int num[15];
void print(){
for (int i = 1;i<=n;i++){
printf("%d",num[i]);
if (i < n)printf(" ");
}
}
bool cmp(int a,int b){
return a>b;
}
int get(){
int sum = 0;
for(int i = 0;i<=n;i++){
sum += num[i] * a[n][i];
if (sum > ssum){
sort(num+i,num+n+1,cmp);
// 将后面从大到小排序，jiu那么 next_permutation 的值就变小了
return 999999;
}
}
// print();
// printf("\n%d\n",sum);
return sum;
}
int main(){
scanf("%d %d",&n,&ssum);
for (int i = 1;i<=n;i++){
for(int j = 1;j<i;j++){
a[i][j] = a[i-1][j] + a[i-1][j-1];
}
a[i][i] = 1;
}
int fi[n+1];
for (int p = 0;p<=n;p++)fi[p] = a[n][p];
for (int i = 0;i<=n;i++)num[i] = i;
// mmin 跟 mmax 搞反了
sort(fi+1,fi+n+1);
int mmin = 0;
for(int i = 0;i<=n;i++)
mmin += num[i] * fi[i];
// printf("mmin=%d\n",mmin);
int mmax = 0;
for(int i = 0;i<=n;i++)
mmax += num[n+1-i] * fi[i];
// printf("mmax=%d\n",mmax);
if (ssum < mmax || ssum > mmin)return 0;
do{
int now = get();
if (now == ssum) {print();return 0;}
}while(next_permutation(num+1, num+n+1));
return 0;
}
7 记忆化 DFS AC
// 2020-03-08 08:51:00
# include <cstdio>
# include <vector>
using namespace std;
int r,c,g[101][101],vis[101][101] = {},res[101][101] = {};
int mmax = 0,maxl = 0;
int DFS(int x,int y,int depth){
if (res[x][y])return res[x][y];
res[x][y] = 1;
if (x+1 < r && g[x+1][y] < g[x][y]) {
DFS(x+1,y,depth+1);
res[x][y] = max(res[x][y],res[x+1][y] + 1);
}
if (y+1 < c && g[x][y+1] < g[x][y]) {
DFS(x,y+1,depth+1);
res[x][y] = max(res[x][y],res[x][y+1] + 1);
}
if (x-1 >= 0 && g[x-1][y] < g[x][y]) {
DFS(x-1,y,depth+1);
res[x][y] = max(res[x][y],res[x-1][y] + 1);
}
if (y-1 >= 0 && g[x][y-1] < g[x][y]) {
DFS(x,y-1,depth+1);
res[x][y] = max(res[x][y],res[x][y-1] + 1);
}
return res[x][y];
}
int main(){
scanf("%d %d",&r,&c);
for (int i = 0;i<r;i++){
for (int j = 0;j<c;j++){
scanf("%d",&g[i][j]);
}
}
for(int i = 0;i<r;i++){
for (int j = 0;j<c;j++){
res[i][j] = DFS(i,j,1);
maxl = maxl > res[i][j] ? maxl : res[i][j];
}
}
printf("%d",maxl);
return 0;
}
记忆化模板：
int DFS(int x){
if (meet) return res[x];
for (next_step){
res[x] = max(res[x],res[next]+1)
}
return res[x];
}
8 自然数拆分 AC
DFS 模板题
# include <cstdio>
# include <vector>
using namespace std;
int n;
vector<int>v;
void DFS(int i,int left){
if (left == 0){
for(int p = 0;p<v.size();p++){
printf("%d",v[p]);
if (p<v.size()-1)printf("+");
}
printf("\n");
}
else{
for(int j = i;j<=left;j++){
v.push_back(j);
DFS(j,left-j);
v.erase(v.end()-1);
if (v.size() == 0)break;
}
}
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n/2;i++)DFS(i,n);
}
9 数联通区域数 AC
BFS ：TLE
//# 2020-03-10 09:05:02
// 换行符的输入要放在哪一行的前面！
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n,m,vis[101][101] = {},g[101][101] = {};
int dir[8][2] = {{1,0},{0,1},{1,-1},{1,1},{-1,0},{0,-1},{-1,1},{-1,-1}};
char c;
struct node{
int x,y;
node(int _x,int _y):x(_x),y(_y){}
};
void BFS(int x,int y){ // 超时
queue<node>q;
q.push(node(x,y));
while(!q.empty()){
int tx = q.front().x,ty = q.front().y;
q.pop();
vis[tx][ty] = 1;
for(int i = 0;i<8;i++){
int nx = tx + dir[i][0],ny = ty + dir[i][1];
if(nx >= 0 && ny >= 0 && nx <n && ny < m
&& vis[nx][ny] == 0 && g[nx][ny] == 1){
q.push(node(nx,ny));
}
}
}
}
void DFS(int tx,int ty){ // ok
for(int i = 0;i<8;i++){
int nx = tx + dir[i][0],ny = ty + dir[i][1];
if(nx >= 0 && ny >= 0 && nx <n && ny < m
&& vis[nx][ny] == 0 && g[nx][ny] == 1){
vis[nx][ny] = 1;
DFS(nx,ny);
}
}
}
int main(){
scanf("%d %d",&n,&m);
vector<node>water;
for (int i = 0;i<n;i++){
scanf("%*c");
for(int j = 0;j<m;j++){
scanf("%c",&c);
if (c == 'W'){
g[i][j] = 1;
water.push_back(node(i,j));
}
}
}
int count = 0;
for(int p = 0;p<water.size();p++){
int i = water[p].x,j = water[p].y;
if (vis[i][j] == 0){
DFS(i,j);
count ++;
}
}
// for(int i = 0;i<n;i++){
// for(int j = 0;j<m;j++){
// printf("%d ",g[i][j]);
// }printf("\n");
// }
printf("%d",count);
return 0;
}
10 DFS AC
# include <cstdio>
# include <algorithm>
using namespace std;
# define min(a,b) a<b?a:b
int ss = 1,tt = 0,n,s[11] = {},t[11] = {},res = 1000000000;
void DFS(int now){
for(int i = now+1;i<n;i++){
ss *= s[i];
tt += t[i];
res = min(abs(ss-tt),res);
DFS(i);
ss /= s[i];
tt -= t[i];
}
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++)scanf("%d %d",&s[i],&t[i]);
DFS(-1);
printf("%d",res);
}
11 选数 DFS + isprime AC
# include <cstdio>
# include <vector>
# include <cmath>
using namespace std;
int n,k,a[21],res = 0,prime[1000000] = {2,3};
vector<int>v;
bool isprime(int p){
for(int i = 0;prime[i] < sqrt(p);i++){
if (p%prime[i] == 0) return false;
}
return true;
}
void getprime(int i){
int count = 0;
for(int j = 2;j<i;j++){
if (isprime(j)) prime[count++] = j;
}
}
bool isprimefast(int num){
for(int i = 0;prime[i] < num+10;i++){
if (prime[i] == num)return true;
}
return false;
}
void DFS(int p,int num){
if (num == k){
int sum = 0;
for(int i = 0;i<v.size();i++){
sum += v[i];
}
if(isprimefast(sum)){
res++;
// printf("sum = %d\n",sum);
}
}else{
for(int i = p+1;i<n;i++){
v.push_back(a[i]);
DFS(i,num+1);
v.erase(v.end()-1);
}
}
}
int main(){
scanf("%d %d",&n,&k);
int total = 0;
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
total += a[i];
}
getprime(total);
// for (int i = 0;i<100;i++)printf("%d ",prime[i]);
DFS(-1,0);
printf("%d",res);
}
12 考前抱佛脚 AC
# include <cstdio>
# define min(a,b) (a) < (b) ? (a) : (b)
int s[4],course[4][21],sum[4],totaltime = 0,grouptime,mintime;
void DFS(int group,int now){
if (grouptime >= (sum[group]+1)/2)
mintime = min(grouptime,mintime);
else {
for(int i = now + 1;i<s[group];i++){
grouptime += course[group][i];
DFS(group,i);
grouptime -= course[group][i];
}
}
}
int main(){
for (int i = 0;i<4;i++)scanf("%d",&s[i]);
for (int i = 0;i<4;i++){
int tempsum = 0;
for(int j = 0;j<s[i];j++){
scanf("%d",&course[i][j]);
tempsum += course[i][j];
}
sum[i] = tempsum;
}
for(int i = 0;i<4;i++){
grouptime = 0,mintime = sum[i];
DFS(i,-1);
// printf("%d|",mintime);
totaltime += mintime;
}
printf("%d",totaltime);
return 0;
}
13 Meteor Shower 56 TODO
# include <cstdio>
# include <cstring>
# define min(a,b) (a)<(b)?(a):(b)
int g[310][310] = {},f[310][310] = {},vis[310][310] = {};
int m,tx,ty,tt,res = 1000000;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void DFS(int x,int y,int step){
if(g[x][y] == 0){
// printf("(%d),%d,%d,%d----",res,x,y,step);
res = min(res,step);
return;
}
else{
for(int i = 0;i<4;i++){
int nx = x+dir[i][0],ny = y + dir[i][1];
if (nx >= 0 && ny >= 0 && vis[nx][ny] == 0 && (g[nx][ny] == 0 || g[nx][ny] > step+1) && step < res){
// step < res 剪枝
// g[nx][ny] > step+1 : +1 !!!
vis[nx][ny] = 1;
DFS(nx,ny,step+1);
vis[nx][ny] = 0;
// 要回溯
}
}
}
}
int main(){
scanf("%d",&m);
for(;m;m--){
scanf("%d %d %d",&tx,&ty,&tt);
// 输入的时候可能不是按照时间顺序输入
if (g[tx][ty] == 0 || g[tx][ty] > tt)g[tx][ty] = tt;
if (tx-1 >= 0 && (g[tx-1][ty] == 0 || g[tx-1][ty] > tt))g[tx-1][ty] = tt;
if (ty-1 >= 0 && (g[tx][ty-1] == 0 || g[tx][ty-1] >tt))g[tx][ty-1] = tt;
if (g[tx+1][ty] == 0 || g[tx+1][ty] > tt)g[tx+1][ty] = tt;
if (g[tx][ty+1] == 0 || g[tx][ty+1] > tt)g[tx][ty+1] = tt;
}
// for (int i = 0;i<5;i++){
// for(int j = 0;j<5;j++){
// printf("%d ",g[i][j]);
// }printf("\n");
// }
DFS(0,0,0);
if (res < 1000000)printf("%d",res);
else printf("-1");
return 0;
}
14 烤鸡 AC
# include <cstdio>
# include <vector>
using namespace std;
int n,total = 0;
vector<int>res;
vector<int>p[10];
void prints(){
// 二维数组下标弄反
for (int j = 0;j<p[0].size();j++){
for(int i = 0;i<9;i++){
printf("%d ",p[i][j]);
}printf("%d\n",p[9][j]);
}
}
void print(){
total++;
for(int i = 0;i<10;i++){
p[i].push_back(res[i]);
}
}
void DFS(int left,int count){
if (count == 10 && left == 0)print();
else {
for(int i = 1;i<=3;i++){
left -= i;
count += 1;
res.push_back(i);
if (!(left + count < 10 || left < 0)) DFS(left,count);
left += i;
count -= 1;
res.pop_back();
}
}
}
int main(){
scanf("%d",&n);
if (n < 10 || n > 30){
printf("0");
return 0;
}
DFS(n,0);
printf("%d\n",total);
prints();
return 0;
}
15 组合数 AC
# include <cstdio>
# include <vector>
using namespace std;
int n,r;
vector<int>res;
void print(){
for(int i = 0;i<r;i++)printf("%3d",res[i]);
printf("\n");
}
void DFS(int now,int count){
if (count == r)print();
else{
for(int i = now+1;i<=n;i++){
res.push_back(i);
DFS(i,count+1);
res.pop_back();
}
}
}
int main(){
scanf("%d %d",&n,&r);
DFS(0,0);
}
数组查找
1 A-B=C AC
# include <cstdio>
# include <map>
using namespace std;
long long n,c,a[200005] = {},ans = 0;
map<long long, long long>m;
int main(){
scanf("%lld %lld",&n,&c);
for(int i = 0;i<n;i++){
scanf("%lld",&a[i]);
m[a[i]]++;
a[i] += c;
}
// for (map<long long, long long>::iterator it = m.begin();it != m.end();it++){
// printf("%lld %lld--", it->first,it->second);
// }
for(int i = 0;i<n;i++){
ans += m[a[i]];
}
printf("%lld",ans);
return 0;
}
2 查找最接近数字 AC
对于upper_bound来说，返回的是被查序列中第一个大于查找值的指针，也就是返回指向被查值>查找值的最小指针，lower_bound则是返回的是被查序列中第一个大于等于查找值的指针，也就是返回指向被查值>=查找值的最小指针。
函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！
# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 100000;
int a[maxn] = {},b,m,n;
long long res = 0;
int main(){
scanf("%d %d",&m,&n);
for(int i = 0;i<m;i++)scanf("%d",&a[i]);
sort(a,a+m);
for(int i = 0;i<n;i++){
scanf("%d",&b);
int pos = (int)(upper_bound(a, a+m, b) - a);
if (pos == 0){
res += (a[pos] - b);
}else if (pos == m){
res += (b - a[pos-1]);
}
else {
int x = a[pos],y = a[pos-1];
res += ((x-b) < (b-y) ? (x-b) : (b-y));
}
// printf("(%d)",a[pos]);
// printf("%d ",res);
}
printf("%lld",res);
return 0;
}
3 查找利率 TODO
理解不了题意，不知道是怎么四舍五入的
# include <cstdio>
# include <algorithm>
# include <cmath>
using namespace std;
double a,sum,each,mon;
bool cool(int x){
double xx = x/10000.0;
printf("%lf ",xx);
double res = 0,p = xx+1;
for(int i = 0;i<mon;i++){
res += int((each)/pow(p,i+1)*100);
}
printf(" %lf\n",res/100.0);
if (abs(res/100.0-sum) < 0.01)return 1;
else return 0;
}
int main(){
scanf("%lf %lf %lf",&sum,&each,&mon);
for(int i= 1;i<40;i++){
if (cool(i)){
printf("%f",(float)i/100.0);
break;
}
}
printf("%f",a);
return 0;
}