//2.1.1递归函数-fib
#include<cstdio>
#include<cstring>int m[100]; //记忆 int fib(int n){if(n<=2) return 1; //出口 if(m[n]!=0) return m[n]; return m[n]=fib(n-1)+fib(n-2); //新学的操作
}
int main(){int n;while(~scanf("%d",&n)&&n){memset(m,0,sizeof(m));printf("fib[%d]=%dn",n,fib(n));}return 0;
}//2.1.2 栈-STL
#include<stack> //c++标准库里的栈
#include<cstdio>
using namespace std;
stack<int> stk;int main(){int a[]={0,1,2,666};stk.push(a[1]);stk.push(a[2]);stk.push(a[3]);printf("#%dn",p()); stk.pop();printf("##%dn",p()); stk.pop();printf("###%dn",p()); stk.pop();return 0;
} //2.1.3 队列
#include<queue>
#include<cstdio>
using namespace std;queue<int> que;int main(){int a[]={0,1,2,666};que.push(a[1]);que.push(a[2]);que.push(a[3]);printf("#%dn",que.front()); que.pop();printf("##%dn",que.front()); que.pop();printf("###%dn",que.front()); que.pop();return 0;
}//2.1.4 DFS-部分和问题
#include<cstdio>int t,k;
int a[25];bool dfs(int n,int r){ //搜到a[n]，需要加r if(r==0) return true; if(n==t) return false; //把a[]搜完都没找到 if(dfs(n+1,r-a[n])) return true; //取a[n] if(dfs(n+1,r)) return true; //不取a[n]return false; //无论取不取 都不存在答案
}int main(){scanf("%d",&t);for(int i=0;i<t;++i){scanf("%d",&a[i]);}scanf("%d",&k);if(dfs(0,k)) printf("Yesn");else printf("Non");return 0;
}
//觉得书上BFS有问题，当然也可能是我的问题。//3.31更新：已解决//2.1.6 特殊状态的枚举-全排列
/*next_permutation(a,a+n);求下一个排列返回值类型 bool求上一个排列：prev_permutation*/
#include<cstdio>
#include<algorithm> //头文件
#include<iostream>
#include<string>
using namespace std;int main(){int a[6]={1,2,3,4,5,6};string s="abc";//输出前n个元素的第x个排列 (字典序) int n=4,x=6;for(int i=1;i<n;i++)next_permutation(a,a+x);for(int i=0;i<x;i++)printf("%d ",a[i]);//同理 do{cout<<s<<endl;//输出所有全排列}while(next_permutation(s.begin(),s.end()));return 0;
}两篇微信排版，一篇新闻稿，两篇原创推送（愚人节、清明节），充实的一天。
——3月30日
看书
//求1-n中与m互质的的数之积
//1.筛素数
//2.用1筛出的素数找m质因子
//3.用2中的质因子打表，标记倍数
//4.遍历累乘#include<cstdio>
#include<cstring>
#define ll long long
const int Max_num=1e5+17;
const ll mod=1e9+7;
bool prim[Max_num];
ll real[Max_num];
ll book[Max_num];
bool a[1000017];
ll n,m;void ol(){int tail=0;for(ll i=2;i<Max_num;++i){if(!prim[i]) real[tail++]=i;for(int j=0;j<tail&&real[j]*i<Max_num;++j){prim[real[j]*i]=true;if(!i%real[j]) break;} }/*for(int i=0;i<tail;++i){printf("%d ",real[i]);}printf("n");*/
}int find(){int index=0;for(int i=0;real[i]*real[i]<=m;++i){//printf("%lld mod %lld=%lldn",m,real[i],m%real[i]);if(m%real[i]==0){ //找到了一个质因子 book[index++]=real[i];while(m%real[i]==0) m/=real[i];}} if(m!=1) book[index++]=m;/*for(int i=0;i<index;++i){printf("%lld ",book[i]);}printf("n");*/return index;
}
/*
//我写的辣鸡代码
ll solve1(int len){ll ans=1;for(ll i=2;i<=n;++i){int flag=1;for(int j=0;j<len&&book[j]<=i;++j){if(i%book[j]==0){//printf("i=%lldn",i);flag=0;break;} }if(flag==1) ans=ans*i%mod;}return ans;
}*///经过hxw大佬开窍
ll solve2(int len){ //遍历 找质因子的倍数跳过，其余相乘；ll ans=1; memset(a,false,sizeof(a));for(int i=1;i<=2*n;++i){for(int j=0;j<len&&book[j]*i<=n;++j){a[i*book[j]]=true;}}for(ll i=1;i<=n;++i){if(!a[i]) ans=ans*i%mod; }return ans;}int main(){ol(); //筛素数while(~scanf("%lld%lld",&n,&m)){int len=find();//筛质因子printf("%lldn",solve2(len)); }return 0;
}
——3月31日
//并查集思路
#include<cstdio>
const int Max_num=1e3;
int a[Max_num];
//a[i]-i为编号 a[i] 为下一个结点编号 int f(int n){ //找链尾 //若a==a[i] 则说明这个节点没有朋友 //否则返回朋友链 尾 return n==a[n] ? n :a[n]=f(a[n]); //注意此处优化！！//return n==a[n] ? n :f(a[n]); //未优化
}void bcj(int i,int j){a[f(i)]=f(j);
}int main(){int n,m,x,y,count=0;scanf("%d%d",&n,&m);for(int i=0;i<n;++i) a[i]=i;for(int i=0;i<m;++i){scanf("%d%d",&x,&y);bcj(x,y);} for(int i=0;i<n;++i){if(a[i]==i) ++count;}printf("%d",count);}
题目：求所有城市都相连的最小代价
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int Max_num=1e5+17;
int a[Max_num];
struct str{int id,fri,len;
}ci[Max_num];int f(int n){ //找尾节点 return n==a[n]?n:a[n]=f(a[n]); //666
} //如果不优化，会TEvoid bcj(int i,int j){a[f(i)]=f(j);
}bool cmp(str a,str b){if(a.len==b.len){return a.id>b.id;}return a.len<b.len;
}int main(){int n,m,s,x,y,d,count=0;ll sum=0;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;++i) a[i]=i;for(int i=0;i<m;++i){ //我觉得d没有用 （对）scanf("%d%d%d",&x,&y,&d);bcj(x,y);}for(int i=0;i<s;++i){ scanf("%d%d%d",&ci[i].id,&ci[i].fri,&ci[i].len);}sort(ci,ci+s,cmp); //按路径小大排序 for(int i=0;i<s;++i){if(f(ci[i].id)!=f(ci[i].fri)){sum+=(ll)ci[i].len;bcj(ci[i].id,ci[i].fri);} }for(int i=1;i<=n;++i){if(a[i]==i) ++count;}if(count>1) printf("Concubines can't do it.n");else printf("%lldn",sum);return 0;
}
——4月1日
这是糟糕的一天，什么都只开了个头，结果什么都没做。
看了动归，卡在完全背包上了，那式子怎么来的真看不懂昂orz。晚上学长讲的那题也听不懂，太菜了，真怕被学长嫌弃，呜呜呜。于是，动归劝退，去看搜索。
学长问我能不能自己写出书上BFS，我发现我写不出。
学长建议我先把搜索学好，emmm，身为蒟蒻，还是先打基础吧，菜得要枯了。（同级大佬@wqq，已经看完网络流了，压力好大，真怕追不上大家进度，我连最短路，最小生成树是什么都不知道）
——4月2日
今天我经历了大学第一次逃课，（终于有逃课经历了！耶！）
形政课逃去隔壁教室打牛客了，害怕有突发状况不敢去别的地方。
这次比赛有题求伴随阵，线代知识，现学现用。（这个事故让我决定清明三天假要自学完线代。//4月9日更新：放假学习，不存在的…
//【入门级BFS】[题目](=3278)//第一遍
/*#include<cstdio>
#include<queue>
using namespace std;const int Max_num=1e5+17;
int book[Max_num]={0};queue<int> q;int main(){int n,k,step=1;scanf("%d%d",&n,&k);int Max_n=k*2;q.push(n);book[n]=1;while(!q.empty()){printf("step=%dn",step);int temp=q.front();if(temp==k){printf("%dn",step);return 0;}int flag=0;if(n+1<Max_n&&!book[n+1]){q.push(n+1);book[n+1]=++step;flag=1;}if(flag){--step;flag=0; }if(n-1>=0&&!book[n-1]){q.push(n-1);book[n-1]=++step;flag=1;}if(flag){--step;flag=0; }if(n*2<=Max_n&&n*2<Max_num&&!book[n*2]){q.push(n*2);book[n*2]=++step;flag=1;}if(flag){--step;flag=0; }q.pop();}return 0;
}*///我想我需要一个结构体
#include<cstdio>
#include<queue>
using namespace std;const int Max_num=1e5;
bool book[Max_num+17];
struct STEP{ //初始化？ int x,step;
}s;queue<STEP> q;int main(){int n,k;scanf("%d%d",&s.x,&k);int Max_n=k*2;s.step=0;q.push(s);while(!q.empty()){STEP a=q.front();if(a.x==k){printf("%d",a.step);return 0;}if(a.x+1<=Max_n&&!book[a.x+1]){STEP b;b.step =a.step+1;b.x=a.x+1;q.push(b);book[b.x]=true;//printf("%dn",b.x);}if(a.x-1>=0&&!book[a.x-1]){STEP b;b.step =a.step+1;b.x=a.x-1;q.push(b);book[b.x]=true;//printf("%dn",b.x);}if(a.x*2<=Max_n&&a.x*2<=Max_num&&!book[a.x*2]){STEP b;b.step =a.step+1;b.x=a.x*2;q.push(b);book[b.x]=true;//printf("%dn",b.x);}q.pop();}return 0;
}
——4月3日
看ICPC WF 直播。莫名激动。
——4月4日
学长让我开始看最短路，终于。
一个上午才勉强弄懂几个最短路算法的原理。以后一定要告诫学弟学妹们，千万不要试图从书上的代码去理解算法（看懵的我浪费了多长时间）。正确姿势是：看书上的文字部分；打开B站，再理解一遍算法的图像演示；然后亲手推一遍（这步很重要）。
下午计划，把上午理解的算法，代码实现一下。不存在的，根本写不出来。写着写着就懵了。
——4月5日
对于最短路，还是敲不出来…自闭
下午和学姐、同届大佬*2一起打了牛客。开心！
最少拐弯数这题，让我对BFS熟练了一丢丢，经过wsw大佬的讲解我才能写出来。他的方法很机智，细节也处理的很好，什么时候能我才能这么强昂，%%%。写完不能AC100%数据，学姐热心帮我看代码，后来我发现我的一个数组下标错了…
wsw大佬教了我构造函数，《挑战》、《白皮》上很多这个操作，终于能看懂了，开心。
S(){} //无参 S(int xx,int yy):x(xx),y(yy){} //两个int参数
新操作
——4月6日
一觉醒来，就天黑了（太真实了）。敲不出最短路的持续自闭。
——4月7日
终于考完高数阶段测验了，TODOLIST少了一大件事。然而这周还有两篇结课论文，有气无力.jpg。
和同级大佬@wqq愉快地讨论了最小拐弯数。
然后他和我说，他看到第四章地逆元那里了…tql。（我…脸上笑嘻嘻，心里）。
莫得感情，菜鸡继续看最短路了。
终于敲出了一题最短路了。
弄懂原理但不会实现，是因为有一些需要用到得知识点，自己有所欠缺：
优先队列是什么
要如何存入带权值的节点，或者说路
如果优先队列类型是结构体；那么它的优先顺序怎么定呢？
注意优先队列的运算符重载。 如果说sort排序规则是cmp，那么优先队列排序规则是(!cmp)，%wsw大佬。
另外，构造函数真好用。
题目：HDU 1874 畅通工程续（板子）
//用迪杰斯特拉实现
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;struct S{int r,v;S(int xx,int yy):r(xx),v(yy){} //真好用bool operator <(const S &a)const{return v>a.v;}
};const int Max_num=207;
const int INF=0x3f3f3f3f;
int n,m;
int d[Max_num];
vector<S> E[Max_num]; //要如何存入带权值的点 ？ 会了。 int main(){while(~scanf("%d%d",&n,&m)){//初始化 for(int i=0;i<=n;++i) E[i].clear();fill(d,d+n+1,INF); for(int i=0;i<m;++i){int x,y,z;scanf("%d%d%d",&x,&y,&z); //存图，因为是无向图E[x].push_back(S(y,z)); E[y].push_back(S(x,z)); } int s,t;scanf("%d%d",&s,&t);priority_queue<S> q;d[s]=0;q.push(S(s,0));while(!q.empty()){//权值只有两个作用 一是作为优先队列的排列根据，二是更新最短路径d[i] //此处只需取出其标号,权值无用 int now&#p().r; q.pop(); for(int i=0;i<E[now].size();++i){int tr=E[now][i].r,tv=E[now][i].v;if(d[tr]>d[now]+tv){d[tr]=d[now]+tv;q.push(S(tr,d[tr]));}}}d[t]==INF?printf("-1n"):printf("%dn",d[t]);}
}
——4月8日
wsw学长桌子空了，看着好吓人，难受。
——4月9日
ccpc省赛热身赛。只写了签到题就去上课了。补题：
题目
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;struct S{int x,y,v;S(int xx,int yy,int vv):x(xx),y(yy),v(vv){}bool operator<(const S &a)const{return v>a.v;}
};
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int n,m,book[507][507],a[507][507];int main(){scanf("%d%d",&n,&m);memset(book,-1,sizeof(book));priority_queue<S> q; for(int i=0;i<n;++i){ for(int j=0;j<m;++j){scanf("%d",&a[i][j]); if(a[i][j]==1){book[i][j]=0; q.push(S(i,j,0));}}}while(!q.empty()){ //BFSS now&#p();q.pop();for(int i=0;i<4;++i){int tx=now.x+dx[i],ty=now.y+dy[i];if(tx>=0&&ty>=0&&tx<n&&ty<m&&(book[tx][ty]<0)){book[tx][ty]=now.v+1;q.push(S(tx,ty,now.v+1));}}}for(int i=0;i<n;++i){for(int j=0;j<m-1;++j){printf("%d ",book[i][j]);}printf("%dn",book[i][m-1]);}return 0;
}
——4月11日
晚上和学姐去看球赛。开心。
——4月12日
第五届CCPC河南省赛
难受。我好想自己打一场比赛呀。
学长很强，我什么忙都帮不上。就在一边看题。
我觉得唯一的贡献就是为学长出了一个测试数据，之后学长找到了wa的原因。
我还有很长的路要走，我觉得以后不能再松懈了，如果一个算法一直不理解，不要死磕浪费时间了，打打比赛，通过题目理解。哪有那么多的奇奇怪怪的东西，刚 就是了。
我也想要带学妹飞。不能想着才大一还有时间。
我已经没有时间了。
打比赛 --> 长见识 --> 补题
死磕书效率太低了。
四月五月学好算法！六月时学好高数与线代，疯狂学！大一上不懂事就算了，大一下已经要明白数学的重要性。
还有就是，学长说的对，不能把书上的板子当成是一个个知识点，而是要把它当成是一个好方法，做题时可以借鉴的好方法。真正的大赛，是不可能有板子的，算法是自己现场想出来的，怎样才能快速地想出自己的算法，这就来自平时写题看书时对各种算法思路的理解与借鉴。即 书上的算法是打怪的经验，而不是打怪的武器。
其实， 拿银我也是很开心的！！！哈哈哈！
晚上打cf爽一爽。
卡题（已补）：第一行长度length；第二行 一个由?()这三个字符的串；求：输出一个括号匹配的串，即把?变为左括号或右括号。//题意并不是这样嗷！！！
题解。
——4月13日
昨天晚上想补补题，wsw和我说C是主席树，有点难先别看（我才不听。
于是我今天早上打开B站（众所周知，B站是个学习网站），看起了主席树：
以下是我的学习历程：
主席树：是可持久化线段树return 线段树是什么？线段树：与树状数组做对比return 嗯？什么是树状数组树状数组：嗯？这是学姐前两天和我说的位运算的运用之一？return 说到学姐，她怎么还不回我消息？
ccpc补题：zzqjuju&lyjuju。
下午找个比赛爽一爽。
卡题：（待补）给定一棵N个点的树，每条边有边权，请你求出最长的一条路径，满足经过每个点最多一次，经过的边的条数为偶数，且边权和最大。
请输出这个最大的边权和。 // 4.15更新：这题是树形dp（学会了再补，溜
——4月14日
补题：点对。
补题：括号匹配【贪心】
优化：字符串去重：（map真好用
//试一试 map 的做法吧？
#include<cstdio>
#include<map>
#include<string>
#include<iostream>
using namespace std;map <string, int> mapp;
string s;int main(){int n,m; scanf("%d%d",&n,&m);while(n--){cin >> s;mapp[s]=1;}printf("%dn",mapp.size());return 0;
}——4月15日
不更了，学长消失了……
本文发布于:2024-02-01 16:04:07，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170677464537804.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
