IT小白

这个屌丝很懒，什么也没留下！

热门标签

考研复试 - 机试模板_考研计算机机试材料

作者：IT小白 | 2024-07-23 14:00:00

踩

考研计算机机试材料

去年开始不让携带纸质资料了，整理一些模板来背一下。

因为没有划定考察范围，时间有限只准备熟悉的，网络流，扩展kmp之类比较难的就不准备了。主要参考《算法笔记》、《明月册》的内容。

机房里只提供Dev C++，用了一下很难用，一个是没有代码单词提示（输入prin不会提示printf），一个是不知道万能头让不让用，还要背一下头文件。

考前必看

仔细看输入输出要求，写完代码对照一下，尤其是特殊情况。

比如：如果无法到达，输出 “WTF”。

这里光计算最短时间就很繁琐，最后终于写好了之后，很可能忘掉不可能的情况，所以最后输出要

特别注意一下output里的条件。

所有提交的代码，提交前必须先自己试几组数据：①最小的情况， ②最大的情况。③正常的情况。
是否需要开long long
数组是否开小，n<=150的开数组开a[155]
1e5以上的数据读入用scanf而不用cin

第0章. C++头文件


#include <stdio.h> // 标准io， printf和scanf和getchar
#include <iostream> // c++io, cin和cout
#include <algorithm> // STL中的sort，__gcd()等一些常用函数
#include <string>  // STL中的string
#include <string.h>  // c普通的字符串，memset()函数
#include <vector> // STL中的vector
#include <set>
#include <map>
#include <queue> // STL中的priority_queue和queue
#include <stack>
#include <cmath>  // acos(), log(), sin()等
#include <stdlib.h> // rand()函数

第一章 - 入门知识点

1.3 二分

题目中，要求输出一个整数答案，满足最大值最小，或最小值最大。

把二分当作一个工具来使用，不是代码的全部。重点是check函数


int main() {
    int left=0, right=100000000;
    while ( left<=right ) {
        int mid = (left+right)/2;
        if ( check(mid)==1 ) {
            ans = mid;
            right = mid-1;
        }
        else left = mid + 1;
    }
    cout << ans << endl;
    
    return 0;
}

1.5 差分

[ L , R ] 区间都+5，只需要 arr[ L ] += 5, arr[ R+1 ] -=5; 最后for循环一遍arr，定义一个变量now一边更新加上去。

题意：n个灯刚开始是关的，m次操作对【L，R】内的全部的灯反转。问最后有几个灯亮着。

思路：刚开始差分直接便利了所有点，T了。所有只需要考虑哪些有贡献的2*m个点就行了，对于区间中哪些0的部分，就不需要遍历了。对于重复的点也不用管。


#include <bits/stdc++.h>
using namespace std;
int n,m,cnt;
struct node {
    int id,x;
}a[3005];
int rule( node a, node b )
{
    return a.id<b.id;
}
int main() {
    cin>>n>>m;
    while ( m-- ) {
        int l,r;cin>>l>>r;
        a[cnt].id = l; a[cnt++].x = 1;
        a[cnt].id = r+1; ar[cnt++].x = -1;
    }
    sort(a,a+cnt,rule);
    int now=0, ans=0;
    for ( int i=0; i<cnt-1; i++ ) {
        now += a[i].x;
        if ( now%2==1 ) {
            ans += a[i+1].id - a[i].id;
        }
    }
    cout << ans << endl;
    
    return 0;
}

1.6 前缀和


二维前缀和，大概率不会考
 
*******
*1    *-1
*     *
*******
-1     -1
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
a[ getid(x1,y1) ] ++;
a[ getid(x1,y2+1) ] ‐‐;
a[ getid(x2+1,y1) ] ‐‐;
a[ getid(x2+1,y2+1) ] ++;
a[ getid(i,j) ] += a[ getid(i‐1,j) ] + a[ getid(i,j‐1) ] ‐ a[ getid(i‐1,j‐1) ];

1.7 STL迭代器


vector<int>::iterator iter; //定义一个名为iter的vector迭代器
map<string,int>::iterator iter; //定义一个名为iter的map迭代器
*iter //对iter进行解引用，返回迭代器iter指向的元素的引用
iter‐>men //对iter进行解引用，获取指定元素中名为men的成员。等效于(*iter).men
++iter //给iter加1，使其指向容器的下一个元素
iter++
‐‐iter //给iter减1，使其指向容器的前一个元素
iter‐‐
iter1==iter2 //比较两个迭代器是否相等，当它们指向同一个容器的同一个元素或者都
//指向同同一个容器的超出末端的下一个位置时，它们相等
iter1!=iter2
    
    
int main()
{
    vector<int> a;
    a.push_back(2); a.push_back(8); a.push_back(5);
    vector<int>::iterator it;
    for ( it=a.begin(); it!=a.end(); it++ ) {
        cout << *it << " ";
    }
    
    map<int,string> mp;
    mp[1] = "ab";
    mp[2] = "sx";
    map<int,string>::iterator it;
    for ( it=mp.begin(); it!=mp.end(); it++ ) {
        cout << it->first << " " << it->second << endl;
    }
    return 0;
}

1.8 闰年+英语月份星期

闰年共有366天（1-12月分别为31天，29天，31天，30天，31天，30天，31天，31天，30天，31天， 30天，31天）普通年有365天（1-12月分别为31天，28天，31天，30天，31天，30天，31天，31天，30天，31天， 30天，31天）

四年一闰，百年不闰，四百年又闰


int isyear(int y) {//判断平年闰年
    if ( y%400==0 || ( y%4==0 && y%100!=0 ) ) return 1;
    return 0;
}

Monday 星期一

Tuesday 星期二

Wednesday 星期三

Thursday 星期四

Friday 星期五

Saturday 星期六

Sunday 星期日，星期天

一月：January二月：February三月：March四月：April五月：May六月：June七月：July八月：August九月：September十月：October十一月：November十二月：December

1.9 离散化

去重函数 + 二分查找


#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    int a[10]={125,14,88,65,44},b[10]={125,14,88,65,44};
    int n = 5;
    sort(b,b+n); //sort(排序)
    int m = unique(b,b+n) - b; // unique(去重)
    for ( int i=0; i<n; i++ ) {
        a[i] = lower_bound(b,b+m,a[i]) - b + 1;
    }   // lower_bound(查找)
    for ( int i=0; i<n; i++ ) {
        cout << a[i] << " ";
    }
    return 0;
}

第二章 - 数论

2.1 最大公约数和最小公倍数


#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n,m;cin >> n >> m;
    cout << __gcd(n,m) << " " << n*m/__gcd(n,m) << endl;
    // 最大公约数， 最小公倍数
    // 2 4  --- 2 4
    // 15 5 --- 5 15
    // 38 4 --- 2 76
    return 0;
}

2.2 素数

欧拉筛


#include <string.h>
#include <iostream>
using namespace std;
const int maxn = 2e6;
int primes[maxn+10],cnt;
bool isprime[maxn+10];
void get_prim()
{
    memset(isprime,true,sizeof(isprime));
    for ( int i=2; i<=maxn; i++ ) {
        if ( isprime[i]==true ) primes[cnt++]=i;
        for ( int j=0; j<cnt&&i*primes[j]<=maxn; j++ ) {
            isprime[ i*primes[j] ] = false;
            if ( i%primes[j]==0 ) break; // 优化点
        }
    }
}
int main()
{
    get_prim();
    for ( int i=0; i<100; i++ ) cout << primes[i] << " ";
    
    return 0;
}

2.3 唯一分解定理

一个数n肯定能被分解成 n = $p1^{a1}*p2^{a2}*...*pn^{an}$ . 因为一个数肯定是由合数和质数构成的，合数又可以分解成质数和合数，最后递归下去就会变成质数的乘积。比如36 = 2 * 2 * 3 * 3

2.5 组合数计算

还一种是根据组合数定义来算

$C_{n}^{m} =$ $\frac{n!}{m!*(n-m)!}$ , 预处理出n以内的阶乘及其逆元。


int C( int n, int m )
{
    if ( n<m ) return 0;
    int ans = ((a[n]*b[m])%mod*b[n-m])%mod;
    return ans;
}
 
a[0]=a[1]=1;
for ( int i=2; i<=1003; i++ ) a[i]=(a[i-1]*i)%mod;
for ( int i=0; i<=1003; i++ ) b[i]=qpow(a[i],mod-2);

2.6 快速幂

记得开long long 和取模


ll qpow( ll a, ll n )
{
    ll re = 1;
    while ( n ) {
        if ( n&1 ) {
            re = (re*a)%mod;
        }
        n >>= 1;
        a = (a*a)%mod;
    }
    return re;
}

2.7 除法分块

第三章 - 树

3.1 BFS和DFS


#include<bits/stdc++.h>
 
using namespace std;
 
struct node {
    int x,y,step;
}t,d;
int nxt[4][2] = {0,1,0,-1,1,0,-1,0};
int via[1005][1005];
 
int bfs( int x, int y )
{
    queue<node> Q;
    t.x = x; t.y = y; t.step=0;
    Q.push(t);via[t.x][t.y]=1;
    while ( !Q.empty() ) {
        t = Q.front(); Q.pop();
        if ( t.x & t.y 符合条件 ) return step;
        for ( int i=0; i<4; i++ ) {
            下一步的情况...
            d.x = t.x+nxt[i][0];
            d.y = t.y+nxt[i][0];
            d.step = t.step+1;
            if ( d.x & d.y 越界 ) continue ;
            if ( via[d.x][d.y]==0 ) { // 之前没出现过的情况
                Q.push(d);
                via[d.x][d.y] = 1;
            }
        }
    }
    return -1;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int a[22];
int n;
ll ans = 0;
 
void dfs( int node, int presum ) // 当前点，之前点的值
{
    if ( node==n+1 ) {
        return ;
    }
    ll temp = presum|a[node];
    ans += temp;
    dfs(node+1,temp);    // 当前点参与运算
    dfs(node+1,presum);  // 当前点没有参加运算
}
 
int main()
{
    int i;
    cin >> n;
    for ( i=1; i<=n; i++ ) cin >> a[i];
    bfs(1,0);
    cout << ans << endl;
 
    return 0;
}

第四章 - 图

4.1 图的存储和遍历

有权图


#include<bits/stdc++.h>
using namespace std;
int maxn = 2e5+10;
int head[maxn],cnt;
struct edge {
    int to,w,nxt;
}e[maxn];
int n,m;
void add( int u, int v, int w )
{
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
}
int main()
{
    memset(head,-1,sizeof(head)); cnt=0;
    cin>>n>>m;
    for ( int i=0; i<m; i++ ) {
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w); // 单向建边
        add(v,u,w);
    }
    int x = 3; // 遍历点x=3的临边
    for ( int i=head[x]; i!=-1; i=e[i].nxt ) {
        int y = e[i].to; 
        int w = e[i].w;
        一些操作.....
    }
    
    return 0;
}

无权图


#include<bits/stdc++.h>
using namespace std;
int maxn = 2e5+10;
vector<int> G[maxn];
int main()
{
    cin>>n>>m;
    for ( int i=0; i<m; i++ ) {
        int u,v;scanf("%d %d",&u,&v);
        e[i].u=min(u,v);e[i].v=max(u,v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    // 遍历u点相邻的点，无权图无法存边权
    for ( int i=0; i<G[u].size(); i++ ) {
        int v = G[u][i];
        // u->v有一条边...
    }
    
    return 0;
}

4.2 最短路

P4779 【模板】单源最短路径（标准版）

已ac放心看


#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int head[maxn],cnt;
struct edge{
    int to,nxt,w;
}e[maxn*2];
struct node {
    int v,dis;
}t,d;
int n,m,s;
int dis[maxn],via[maxn];
bool operator<( const node& a, const node& b )
{
    return a.dis>b.dis;  //重点！！是大于
}
void add( int u, int v, int w )
{
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
}
void dij( int s )
{
    memset(via,0,sizeof(via));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    priority_queue<node> Q;
    t.v = s; t.dis=0;
    Q.push(t);
    while ( !Q.empty() ) {
        if ( via[ Q.top().v ]==1 ) {
            Q.pop();
            continue ;
        }
        t = Q.top(); Q.pop();
        int u = t.v;
        dis[u] = t.dis;
        via[u] = 1;
        for ( int i=head[u]; i!=-1; i=e[i].nxt ) {
            int v = e[i].to, w=e[i].w;
            if ( via[v]==0 && dis[v]>dis[u]+w ) {
                dis[v] = dis[u]+w;
                d.v = v;
                d.dis = dis[v];
                Q.push(d);
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head)); cnt=0;
    cin>>n>>m>>s;
    for ( int i=0; i<m; i++ ) {
        int u,v,w;scanf("%d %d %d",&u,&v,&w);
        add(u,v,w);
    }
    dij(s);
    for ( int i=1; i<n; i++ ) printf("%d ",dis[i]);
    printf("%d\n",dis[n]);
    return 0;
}

4.3 最小生成树


#include<bits/stdc++.h>
 
using namespace std;
 
struct node {
	int from,to,w;
}a[105*105];
int n,cnt,ans,pos;
int pre[105];
 
int rule( node a, node b )
{
	return a.w<b.w;
}
 
int root( int x )
{
	if ( pre[x]!=x ) {
		pre[x] = root(pre[x]);
	}
	return pre[x];
}
 
int join( int a, int b, int w )
{
	int x = root(a);
	int y = root(b);
	if ( x!=y ) {
		pre[x] = pre[y];
		ans += w;
		pos ++;
	}
}
 
int main() {
	cin>>n;
	for ( int i=0; i<=n; i++ ) pre[i]=i;
	cnt = 0; ans=0; pos=0;
	for ( int i=1; i<=n; i++ ) {
		for ( int j=1; j<=n; j++ ) {
			int x;scanf("%d",&x);
			if ( i==j ) continue;
			a[cnt].from = i;
			a[cnt].to = j;
			a[cnt++].w = x;
		}
	}
	sort(a,a+cnt,rule);
	for ( int i=0; i<cnt; i++ ) {
		join(a[i].from,a[i].to,a[i].w);
		if ( pos==n-1 ) break;
	}
	cout << ans << endl;
	
	return 0;
}

4.4 拓扑排序


void topu()
{
    queue<int> Q; // 队列只存入度为0的点
    for ( int i=1; i<=n; i++ ) {
        if ( in[i]==0 ) Q.push(i);
    }
    vector<int> ans; // 存拓扑序列
    while ( !Q.empty() ) {
        int t = Q.front(); Q.pop(); // 选一个入度为0的点出来
        ans.push_back(t);
        for ( int i=head[t]; i!=-1; i=e[i].nxt ) {
            int to = e[i].to;
            in[to]--;  // 相连点度数--
            if ( in[to]==0 ) Q.push(to);
        }
    }
    
    return 0;
}

4.5 dfs判负环 *

第五章 - 动态规划

5.1 背包问题

01 背包 有n 种不同的物品（每个物品只有一件），每个物品有两个属性，weight 体积，value 价值，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。

完全背包 如果物品不计件数，就是每个物品不只一件的话。

01背包问题与完全背包问题 代码非常相似一个是从后往前遍历，一个是从前往后遍历。

01背包


#include <bits/stdc++.h>
 
using namespace std;
 
int dp[1005];
int price[1005];
int weight[1005];
 
int main()
{
    int n,tot;
    while ( cin>>n>>tot ) {
        memset(dp,0,sizeof(dp));
        for ( int i=1; i<=n; i++ ) cin>>weight[i]>>price[i];
        for ( int i=1; i<=n; i++ ) {
            for ( int j=tot; j>=1; j-- ) {
                if ( j>=weight[i] ) {
                    dp[j] = max( dp[j], dp[j-weight[i]]+price[i] );
                }
            }
        }
        cout << dp[tot] << endl; // 最多能装多少价值的货物
    }
 
    return 0;
}

完全背包


#include <bits/stdc++.h>
 
using namespace std;
 
int dp[1005];
int price[1005];
int weight[1005];
 
int main()
{
    int n,tot;
    while ( cin>>n>>tot ) {
        memset(dp,0,sizeof(dp));
        for ( int i=1; i<=n; i++ ) cin>>weight[i]>>price[i];
        for ( int i=1; i<=tot; i++ ) {
            for ( int j=1; j<=tot; j++ ) {
                if ( j>=weight[i] ) {
                    dp[j] = max( dp[j], dp[j-weight[i]]+price[i] );
                }
            }
        }
        cout << dp[tot] << endl; // 最多能装多少价值的货物
    }
 
    return 0;
}

恰好装满问题

朴素的背包代码是求小于等于背包体积能装的最大值，但有些时候题目要求背包需要恰好完全装满。

是否恰好装满的解法不同只在于初始值的不同

恰好装满：

求最大值时，除了dp[0] 为0，其他都初始化为无穷小 -0x3f3f3f3f ，for循环里取max

求最小值时，除了dp[0] 为0，其他都初始化为无穷大 0x3f3f3f3f ，for循环里取min

不必恰好装满：

求最大值时，初始化为0

求最小值时，初始化为0

5.2 最大连续子序列和

贪心，for循环累加，小于0，设成0

5.3 最长不下降子序列（LIS）

5.4 最长公共子序列（LCS）

5.5 最长回文子串

5.6 DAG最长路

第六章 - 字符串

6.1 字符串hash

6.2 KMP算法

给定两个字符串 s 和 t ，判断 t 是否为 s 的子串。

第七章 - 数据结构

7.1 线段树lazy模板

7.2 权值线段树

7.3 并查集


#include<bits/stdc++.h>
 
using namespace std;
 
int n,m,k,ans;
int pre[100005];
struct node {
    int from,to,w;
}e[100005*3];
 
int rule( node a, node b )
{
    return a.w>b.w;
}
 
int root( int x )
{
    if ( x!=pre[x] ) {
        pre[x] = root(pre[x]);
    }
    return pre[x];
}
 
int join( int u, int v, int w )
{
    int x = root(u);
    int y = root(v);
    if ( x!=y ) {
        pre[x] = y;
        k --;
        ans += w;
    }
}
 
int main()
{
    ans = 0;
    cin>>n>>m>>k;
    for ( int i=0; i<=n; i++ ) pre[i]=i;
    for ( int i=0; i<m; i++ ) {
        int u,v,w;scanf("%d %d %d",&u,&v,&w);
        e[i].from=u;
        e[i].to = v;
        e[i].w = w;
    }
    sort(e,e+m,rule);
    for ( int i=0; i<m; i++ ) {
        join(e[i].from,e[i].to,e[i].w);
        if ( k==0 ) break;
    }
    cout << ans << endl;
 
    return 0;
}

7.4 单调栈&单调队列

对于单调队列，我们这样子来定义：

1、维护区间最值

2、去除冗杂状态如上题，区间中的两个元素a[i],a[j]（假设现在再求最大值）若 j>i且a[j]>=a[i] ，a[j]比a[i]还大而且还在后面（目前a[j]留在队列肯定比a[i]有用，因为你是往后推，核心思想 !!!）

3、保持队列单调，最大值是单调递减序列，最小值反之

4、最优选择在队首

单调队列实现的大致过程： 1、维护队首（对于上题就是如果队首已经是当前元素的m个之前，则队首就应该被删了,head++） 2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态，保持单调性）

简单举例应用 数列为：6 4 10 10 8 6 4 2 12 14 N=10,K=3; 那么我们构造一个长度为3的单调递减队列：首先，那6和它的位置0放入队列中，我们用(6,0)表示，每一步插入元素时队列中的元素如下插入6：(6,0); 插入4：(6,0),(4,1); 插入10：(10,2); 插入第二个10，保留后面那个：(10,3); 插入8：(10,3),(8,4); 插入6：(10,3),(8,4),(6,5); 插入4，之前的10已经超出范围所以排掉：(8,4),(6,5),(4,6); 插入2，同理：(6,5),(4,6),(2,7); 插入12：(12,8); 插入14：(14,9); 那么f(i)就是第i步时队列当中的首元素：6,6,10,10,10,10,8,6,12,14 同理，最小值也可以用单调队列来做。

单调队列的时间复杂度是O（N），因为每个数只会进队和出队一次，所以这个算法的效率还是很高的。注意：建议直接用数组模拟单调队列，因为系统自带容器不方便而且不易调试，同时，每个数只会进去一次，所以，数组绝对不会爆，空间也是S（N），优于堆或线段树等数据结构。

更重要的：单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调队列或类似于单调队列的方法去除冗杂状态，保存我们想要的状态，


#include <iostream>
#include <stdlib.h>
#include <stdio.h>
 
using namespace std;
 
const int maxn = 1e6+10;
struct node {
    int date,time;
} v[maxn],t,d; // 模拟单调队列
int n,k;
int a[maxn];
int Max[maxn];
int Min[maxn];
int cnt;
int head=1,tail=0; // 记住这个设定
 
void getmax()
{
    head=1;tail=0;
    t.date=a[0]; t.time=k; v[++tail]=t; // 把第一个值放进队列
    Max[0] = v[head].date;
    for ( int i=1; i<n; i++ ) {
        if ( v[head].time<=i ) head++;  // 检验队头元素是否过期
        t.date = a[i];
        t.time = i+k;
        while ( t.date>=v[tail].date && head<=tail ) { 
            tail --;                     // 当前元素从队尾插入，并保持队列单调
        }
        v[++tail] = t;
        Max[i] = v[head].date; // 更新当前状态的答案
    }
 
    for ( int i=k-1; i<n-1; i++ ) {
        cout << Max[i] << " ";
    }
    cout << Max[n-1] << endl;
}
 
void getmin()
{
    head=1;tail=0;
    t.date=a[0]; t.time=k; v[++tail]=t;
    Min[0] = v[head].date;
    for ( int i=1; i<n; i++ ) {
        if ( v[head].time<=i ) head++;
        t.date = a[i];
        t.time = i+k;
        while ( t.date<=v[tail].date && head<=tail ) {
            tail --;
        }
        v[++tail] = t;
        Min[i] = v[head].date;
    }
 
    for ( int i=k-1; i<n-1; i++ ) {
        cout << Min[i] << " ";
    }
    cout << Min[n-1] << endl;
}
 
int main()
{
    cin >> n >> k;
    for ( int i=0; i<n; i++ ) {
        scanf("%d",&a[i]);
    }
    getmin();
    getmax();
 
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/870188