am
1.数塔问题：
水题
2.回家的路：
最短路水题，最大的用处是让我想起了自己已经写不来优化DJ了。
3.真二叉树的重构：
和前一天的二叉树差不多（甚至还简单一点），关键在于在前序中所有子节点在当前节点的后面，后序中所有子节点在后面。用队列模拟就行了。
指针！！！
#include<bits/stdc++.h>
using namespace std;
struct tr{
int x;
tr *l;
tr *r;
};
int n,i;
int a[1010],b[1010];
inline void pre(tr *p){
if(i<n){
i++;
p->x=a[i];
p->l=new tr;
p->r=new tr;
if(i==n){
p->l=NULL;
p->r=NULL;
return ;
}
if(b[a[i+1]]<b[a[i]]){
pre(p->l);
pre(p->r);
} else {
p->l=NULL;
p->r=NULL;
}
}
}
inline void po(tr *p) {
if(p!=NULL) {
po(p->l);
cout<<p->x<<" ";
po(p->r);
}
else return ;
}
int main(){
cin>>n;
for(int j=1;j<=n;j++){
cin>>a[j];
}
for(int j=1;j<=n;j++){
int x;
cin>>x;
b[x]=j;
}
tr *p=new tr;
p->l=NULL;
p->r=NULL;
pre(p);
po(p);
return 0;
}
/*
5
1 2 4 5 3
4 5 2 3 1
*/
4.car:
数学问题。根据小学奥数，肯定是两个人同时到达时间是最短的（因为同时必定有车+两个人的速度）。
5.最大整数
直接sort 需重载运算符 对于两个串a和b，以31和312为例，比较a+b和b+a，也就是31231和31312的大小；排好序后从第一个依次输出就可以了
bool operator < (node x,node y){
char z[330];
char w[330];
strcpy(z,x.a);
strcpy(z+strlen(z),y.a);
strcpy(w,y.a);
strcpy(w+strlen(w),x.a);
return strcmp(z,w)>=0 ? true : false;
}
6.整数区间
贪心板题
7.最少转弯问题
直接深搜，注意剪枝，可能不是正解，但过了
#include<bits/stdc++.h>
#define nx x+dx[i]//学会多用define
#define ny y+dy[i]
using namespace std;
int dx[4]={0,1,0,-1},
dy[4]={1,0,-1,0};
bool v[111][111];
int d[111][111];
int n,m,X,x2,Y,y2;
inline void dfs(int x,int y,int to){//当前在哪和朝向
if(x==x2 && y==y2){
return ;
}
if(d[x][y]>d[x2][y2] && d[x][y]!=0x3f3f3f3f){
return ;
}
int i=to;
if(v[nx][ny] && d[nx][ny]>d[x][y]){//直走
d[nx][ny]=d[x][y];
dfs(nx,ny,i);
}
i=(to+1)%4;
if(v[nx][ny] && d[nx][ny]>d[x][y]+1){//右转
d[nx][ny]=d[x][y]+1;
dfs(nx,ny,i);
}
i=(to+3)%4;
if(v[nx][ny] && d[nx][ny]>d[x][y]+1){//左转
d[nx][ny]=d[x][y]+1;
dfs(nx,ny,i);
}
}
int main(){
memset(d,0x3f,sizeof(d));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];
v[i][j]^=1;
}
}
scanf("%d%d%d%d",&X,&Y,&x2,&y2);
for(int i=0;i<4;i++){
d[X][Y]=0;
dfs(X,Y,i);
}
cout<<d[x2][y2];
return 0;
}
/*
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
*/
?8.单词的划分
字典树储存然后深搜
#include<bits/stdc++.h>
using namespace std;
int t,m,n;
char x[110];
char c[110];
struct Trie {
int son[26];
int num;
}a[100000];
inline void stick_in() {
int l,p=0;
l=strlen(x);
for(int i=0;i<l;i++) {
if(a[p].son[x[i]-'a']==0)
a[p].son[x[i]-'a']=++t;
p=a[p].son[x[i]-'a'];
}
a[p].num=1;//标记这是单词结尾
}
int l,ans;
inline void get_answer(int k,int tmp) {//k为当前位置，tmp记录答案
if(tmp>=ans) return ;//当前已超过已有答案
if(k==l){//更新
ans=tmp;
return ;
}
int p=0;//每次都从字典树开头开始搜
for(int i=k;i<l;i++) {
if(a[p].son[c[i]-'a']==0) break;
p=a[p].son[c[i]-'a'];
if(a[p].num==1)//找到一个单词，就从下一个位置继续搜
get_answer(i+1,tmp+1);
}
}
int main() {
scanf("%s",c);
l=strlen(c);
ans=l+1;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s",x);
stick_in();
}
get_answer(0,0);
printf("%d\n",ans);
return 0;
}
?9.众数
水题
?pm
?1.回文日期
显然总共的合法回文日期没有多少 所以。。。直接打表
#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt;
int a[10000];
inline bool check(int k){//检查是否合法
k%=10000;
int y=k/100;
int x=k%100;
if(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12){
if(x<=31) return true;
} else if(y==4 || y==6 || y==9 || y==11){
if(x<=30) return true;
} else if(y==2){
if(x<=28) return true;//不用管29号后面特判
}
return false;
}
inline int mak(int k){
int x=0,y=k;
x+=(y%10)*1000;
y/=10;
x+=(y%10)*100;
y/=10;
x+=(y%10)*10;
y/=10;
x+=y;
x+=k*10000;
return x;
}
int main(){
for(int i=1000;i<=9999;i++){//根据年份造日期
int x=mak(i);
if(check(x)){
a[cnt++]=x;
}
else if(x==92200229) a[cnt++]=x;//29号的只有这一天
}
scanf("%d%d",&n,&m);
int p1=lower_bound(a,a+cnt,n)-a;//第一个大于等于n
int p2=upper_bound(a,a+cnt,m)-a;//第一个大于m
cout<<p2-p1;
return 0;
}
/*
20111102
20111102
*/
2.gcd
水题
3.校门外的树
万能的sort，将左端点作为第一关键字，右端点最为第二关键字
sort(p+1,p+m+1);
p[m+1].l=20000;
int L=-1,R=-2;
for(int i=1;i<=m+1;i++){
int le=p[i].l,ri=p[i].r;
if(le<=R) R=max(R,ri);
else{
ans+=(R-L+1);
L=le,R=ri;
}
}
4.蛇形方阵
二维数组入门题
#include<bits/stdc++.h>
using namespace std;
#define nx x+xx[k]
#define ny y+yy[k]
int n,m;
int xx[2]={1,-1},yy[2]={1,-1};
int a[31][31];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k=i%2,x,y;
if(k==1) x=i,y=n;
if(k==0) x=1,y=n-i+1;
for(int j=1;j<=i;j++){
a[x][y]=++m;
a[n-x+1][n-y+1]=(n*n+1-m);
x=nx,y=ny;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<setw(5)<<a[i][j];
cout<<endl;
}
return 0;
}
5.单点修改，区间查询
树状数组入门知识
6.溶液模拟器
用栈就行
#include<bits/stdc++.h>
using namespace std;
int v;
double b[10010],c;
int a[10010],r;
int n;
int main(){
scanf("%d%lf",&v,&c);
r++;
a[r]=v;
b[r]=c;
scanf("%d",&n);
for(int i=1;i<=n;i++){
char op[2];
scanf("%s",op);
if(op[0]=='P'){
scanf("%d%lf",&v,&c);
r++;
a[r]=a[r-1]+v;
b[r]=(a[r-1]*b[r-1]+v*c)/(a[r]*1.0);
}
else if(r!=1) r--;
printf("%d %.5lf\n",a[r],b[r]);
}
return 0;
}
/*
100 100 2 P 100 0 Z
*/
6.转圈游戏
公式题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,x;
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
ll y=1,z=10;
while(k){//快速幂
if(k&1) y=y*z%n;
z=z*z%n;
k>>=1;
}
printf("%lld",(m%n*y%n+x%n)%n);//公式
}
7.生日
01背包数据可是2^32次方！硬搜又是2^40次方，经大佬指导学会了对半深搜+hash这么个东西
#include<bits/stdc++.h>
using namespace std;
int n,m,half;
int a[100];
const int q1=9947009,q2=995551;
bool t1[q1+5],t2[q2+5];
inline void dfs(int x,int sum) {
if(sum>m) return;
if(x>half){
t1[sum%q1]=t2[sum%q2]=1;
return;
}
dfs(x+1,sum);
dfs(x+1,sum+a[x]);
}
bool flag=0;
inline void dfs2(int x,int sum) {
if(flag) return;
if(sum>m) return;
if(x>n){
if(t1[(m-sum)%q1]&&t2[(m-sum)%q2]) flag=1;
return;
}
dfs2(x+1,sum);
dfs2(x+1,sum+a[x]);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF) {
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
flag=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
half=n/2;
dfs(1,0);
dfs2(half+1,0);
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
总结
大部分水题，但还在练习基础阶段，勉强过关
|