算法竞赛入门【暑期速成计划】(二)
前言
为什么突然想学算法了?
> 用较为“官方”的语言讲,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言,是因为当下快到了考研和找工作的年纪(ಥ_ಥ),无论走哪一条路,都不免需要一些相对丰富的算法知识,是故,便产生了一个暑假速成算法的计划,可能对于像我这种算法竞赛小白而言,几乎很难,但我仍然还是想尝试一下,毕竟,梦想还是要有的,万一实现了呢?~( ̄▽ ̄~)~
习题训练(码题集)
1. 赌石
【AC代码】
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long double LD;
LD C_div(int k, int n)
{
LD res = 1;
for (int i = n, j = 1; j <= k; i -- , j ++ )
res = res * i / j;
for (int i = 1; i <= k; i ++ ) res /= (LD)4.0;
return res;
}
int main()
{
int n;
cin >> n;
n /= 2;
printf("%.4llf", 1 - C_div(n - 1, 2 * n - 2));
return 0;
}
2. 相对马高
【AC代码】
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
#define ll long long
#define N 21000
ll a[N] = {}, b[N] = {};
struct op{
int a, b;
}s[N];
bool operator < (const op &a, const op &b){
if (a.a == b.a) return a.b < b.b ;
else return a.a < b.a;
}
set<op> p ;
int main(){
ll n, h, m ;
cin >> n >> h >> m;
for(ll i = 1; i <= m; i++){
ll a1,a2;
cin >> a1 >> a2;
if (a1 == a2) continue;
if (a1 > a2) swap(a1,a2);
op f; f.a = a1, f.b = a2 ;
p.insert(f);
}
for (set<op>::iterator i = p.begin(); i != p.end();i++){
op f = *i;
b[f.a + 1] = b[f.a + 1] - 1;
b[f.b] = b[f.b] + 1 ;
}
for (ll i = 1;i <= n; i++){
a[i] = b[i] + a[i - 1] ;
cout << a[i] + h << endl;
}
return 0;
}
3. 小码哥学多重集
【AC代码】
#include <bits/stdc++.h>
using namespace std;
void solve(){
set<int> S;
int n,k;
cin >> n >> k;
int a;
int maxn = -1;
for(int i=1;i<=n;i++){
scanf("%d",&a);
S.insert(a);
maxn = max(maxn,a);
}
int minn = 1e9;
for(int i=0;;i++){
if(S.find(i)==S.end()){
minn = i;
break;
}
}
if(minn<maxn){
if(k>0) S.insert(ceil((maxn+minn)/2.0));
cout << (int)S.size() << '\n';
return;
}else{
cout << ((int)S.size()+k) << '\n';
}
}
int main()
{
int __ = 1;
cin >> __;
while(__--){
solve();
}
return 0;
}
4. 区间完数
【AC代码】
#include<bits/stdc++.h>
using namespace std;
bool check(int x){
if(x==1) return false;
int s = 1;
for(int i=2;i*i<=x;i++){
if(x%i==0){
s += i;
s += (x/i);
}
}
return s==x;
}
int main()
{
int l,r;
cin >> l >> r;
for(int i=l;i<=r;i++){
if(check(i)){
cout << i << ' ';
}
}
cout << '\n';
return 0;
}
5. 都相差6
【AC代码】
#include<stdio.h>
int main()
{
printf("5 11 17 23 29");
return 0;
}
6. 牛顿迭代法
【AC代码】
import java.util.Scanner;
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// code here
double x = 1.5;
double xn = cac1ND(x);
System.out.format("%.6f",xn);
input.close();
}
static double cac1ND(double x){
double x1 = x-(2*x*x*x+4*x*x-7*x-6)/(6*x*x+8*x-7);
if(Math.abs(x1-x)<1e-7){
return x1;
}else{
return cac1ND(x1);
}
}
}
7. 对分法
【AC】代码
import java.util.Scanner;
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// code here
System.out.format("%.6f",duifen(-10,0));
input.close();
}
static double f(double x){
return x*x-6*x-1;
}
static double duifen(double a, double b){
if(Math.abs(a-b)<1e-7){
return a;
}else{
if(f(a) *f((a+b)/2)<0){
return duifen(a, (a+b)/2);
}else{
return duifen((a+b)/2, b);
}
}
}
}
8. 买马
【AC代码】
#include<stdio.h>
int main()
{
int n,s[200];
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
}
for(int k=1;k<=1000;k++){
int b[1005]={0},flag=1;
for(int j=0;j<n;j++){
if(b[s[j]%k]==0){
b[s[j]%k]=1;
}else{
flag=0;
break;
}
}
if(flag){
printf("%d\n",k);
break;
}
}
return 0;
}
9. 鸽子洞
【AC代码】
#include <iostream>
using namespace std;
int main( )
{
long long n, m;
cin >> n >> m;
int res = n / m;
if (n % m) res ++ ;
cout << res << endl;
return 0;
}
10. 饿饿! 饭饭!
【AC代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans = 1;
int main( )
{
int n,k,w;
cin>>n>>k>>w;
w*=3;
if(w>k) ans=0;
for(int i =k-w+1; i<=k;i++) ans*=i;
cout<<ans<<endl;
return 0;
}
11. 打折
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int a[222];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
int ans=0;
int now=0;
for(int i=1;i<=n;i++){
if(a[i]<0&&now<m){
ans-=a[i];
now++;
}else{
break;
}
}
printf("%d\n",ans);
return 0;
}
12.队列操作
【AC代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,q,u,v,t;
int h1,h2,h3,t1,t2,t3;
int q1[8000001],q2[8000001],q3[8000001];
int cmp(int a,int b){
return a>b;
}
int pop1(int time){
int top1=-1,top2=-1,top3=-1;
if(h1<=t1){
top1=q1[h1]+(time-1)*q;
}
if(h2<=t2){
top2=q2[h2]+(time-h2-1)*q;
}
if(h3<=t3){
top3=q3[h3]+(time-h3-1)*q;
}
int k=1;
if(top1<top2){
k=2;
}
if(top3>max(top1,top2)){
k=3;
}
switch(k){
case 1:h1++;return top1;break;
case 2:h2++;return top2;break;
case 3:h3++;return top3;break;
}
}
void push1(int x){
int p1=1LL*x*u/v;
int p2=x-p1;
if(p1<p2){
swap(p1,p2);
}
q2[++t2]=p1;
q3[++t3]=p2;
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=1;i<=n;i++){
scanf("%d",&q1[i]);
}
sort(q1+1,q1+n+1,cmp);
h1=1;
h2=1;
h3=1;
t1=n;
t2=0;
t3=0;
int top;
for(int i=1;i<=m;i++){
top=pop1(i);
if(i%t==0){
printf("%d ",top);
}
push1(top);
}
printf("\n");
for(int i=1;i<=n+m;i++){
top=pop1(m+1);
if(i%t==0){
printf("%d ",top);
}
}
return 0;
}
13.奇偶性
【AC代码】
#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
inline int read() {
int ans = 0, f = 1;
char ch = getchar();
if (ch == '-')
f *= -1;
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
ans = ans * 10 + ch - '0';
ch = getchar();
}
return ans * f;
}
void Merge(int A[], int L, int Mid, int R) {
int *Temp = (int *)malloc((R - L + 1) * sizeof(int));
int p = L, q = Mid, k = 0;
while (p <= Mid - 1 && q <= R) {
if (A[p] <= A[q])
Temp[k++] = A[p++];
else {
Temp[k++] = A[q++];
ans += Mid - p;
}
}
while (p <= Mid - 1)
Temp[k++] = A[p++];
while (q <= R)
Temp[k++] = A[q++];
for (int i = 0; i < k; i++)
A[i + L] = Temp[i];
}
void MSort(int A[], int L, int RightEnd) {
if (L < RightEnd) {
int mid = (L + RightEnd) / 2;
MSort(A, L, mid);
MSort(A, mid + 1, RightEnd);
Merge(A, L, mid + 1, RightEnd);
}
}
int main() {
int n, t, l, r, A[100005];
n = read();
for (int i = 0; i < n; i++)
A[i] = read();
MSort(A, 0, n - 1);
ans %= 2;
scanf("%d", &t);
while (t--) {
l = read(), r = read();
int p = r - l + 1;//区间长度
if ((p * (p - 1) / 2 % 2))//判断区间反转次数p*(p-1)/2的奇偶
ans ^= 1;//改变奇偶性
if (ans)
printf("1\n");
else printf("0\n");
}
return 0;
}
14. 标记祖先
【AC代码】
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define INF 0x3fffffff
int pre[100005];//用于保存树形结构
int mark[100005];//用于存放各结点最早的标记时间
typedef pair<int, int>P;
P Q[100005];//second 表示查询的时间 first表示查询的对象
void init(int n) {
for (int i = 1; i <= n; i++) {
pre[i] = -1;
mark[i] = INF;
}
//pre[1] = 1;
mark[1] = 0;//事先标记根结点
}
int findroot(int x, int y) {
if (mark[x] < y) {//该点在查询之前已经标记
return x;
}
else {
int tmp = findroot(pre[x], y);
/*路径压缩 按时间顺序倒序处理查询
那么该时间之后的mark操作就没有意义了,可直接进行路径压缩
将路径上的点进行路径压缩,直到到达在该时间之前的一次mark操作那里
*/
pre[x] = tmp;
return tmp;
}
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
if (n == 0 && m == 0) break;
init(n);
for (int i = 2; i <= n; i++) {
scanf("%d", &pre[i]);
}
long long ans = 0;
int cnt = 0;//查询的个数
for (int i = 1; i <= m; i++) {
char op; int tmp;
scanf("\n%c%d", &op, &tmp);
if (op == 'M') {
mark[tmp] = min(i, mark[tmp]);//存放最早的标记时间
}
else if (op == 'Q') {
Q[++cnt] = P(tmp, i);
}
}
for (; cnt > 0; cnt--) {
ans += findroot(Q[cnt].first, Q[cnt].second);
}
cout << ans << endl;
}
}
15. 活动安排
【AC代码】
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
PII t[500010];
bool cmp(PII a,PII b){
return a.second<b.second;
}
int main( )
{
int n;
cin >> n;
int l,r;
for(int i=1;i<=n;i++){
scanf("%d%d",&l,&r);
t[i] = make_pair(l,r);
}
sort(t+1,t+1+n,cmp);
r = t[1].second;
int ans = 1;
for(int i=2;i<=n;i++){
if(r<=t[i].first){
r = t[i].second;
ans++;
}
}
cout << ans <<endl;
return 0;
}
16. 滚动的小球
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,l,r;
scanf("%d%d%d",&n,&l,&r);
int x;
int ans1 = -1,ans2 = n+1;
for(int i=1;i<=l;i++){
scanf("%d",&x);
ans1 = max(ans1,x);
}
for(int i=1;i<=r;i++){
scanf("%d",&x);
ans2 = min(ans2,x);
}
ans2 = n - ans2;
int ans;
if(l && !r){
ans = ans1;
}else if(r && !l){
ans = ans2;
}else{
ans = max(ans1,ans2);
}
cout<<ans<<endl;
return 0;
}
17. 第k小函数值
【AC代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
int a,b,c;
}node[30];
ll w[1000010];
ll p[1000010];
int total;
ll calc(int a,int b,int c,int x){
return (ll)a*x*x + (ll)b*x+c;
}
int main( )
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
}
int x = 1;
int ans = 0;
bool f = 0;
while(true){
if(total>=k){
if(f){
memcpy(p,w,sizeof(ll)*(k+1));
sort(w+1,w+1+total);
bool flag = 1;
for(int i=1;i<=k;i++) if(w[i]!=p[i]){
flag = 0;
break;
}
if(flag){
ans = w[k];
break;
}
}else{
f = 1;
}
}
for(int i=1;i<=n;i++){
w[++total] = calc(node[i].a,node[i].b,node[i].c,x);
}
x++;
}
cout<<ans<<endl;
return 0;
}
18. 栈的min
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int total;
int sk[1000010];
int main( )
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
if(t==1){
int x;
scanf("%d",&x);
sk[++total] = x;
}else if(t==2){
if(total>=1) total--;
}else if(t==3){
printf("%d\n",sk[total]);
}else{
int ans = 1e9;
for(int i=1; i<=total;i++) ans = min(ans,sk[i]);
printf("%d\n",ans);
}
}
return 0;
}
19. 赋值
【AC代码】
// 给定一张含有n个结点m条边的无向图,每条边的两个端点奇偶性必须不同,有多少种不同的赋值方式
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
const ll mod = 1e9 + 7;
vector<int> a[300010]; // 存图
ll Pow[300010] = {1}; // Pow[i] = 2^i
int color[300010] = {0}; // 分组情况,默认值0表示未分组
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) { // 预处理,计算2^i
Pow[i] = (Pow[i - 1] * 2) % mod;
}
for (int i = 0; i < m; i++) { // 读入图
int l, r;
scanf("%d%d", &l, &r);
a[l].push_back(r);
a[r].push_back(l);
}
ll ans = 1; // 答案
for (int i = 1; i <= n; i++) { // 遍历所有节点
if (!color[i]) { // 还没被染色(说明还没有被划分到某个子图中)
int aNode = 0, bNode = 0; // 二分图A、B中的节点个数
queue<int> q; // bfs队列
function<void(int, int)> addOneNode = [&](int thisNode, int thisColor) { // 处理一个新的节点
color[thisNode] = thisColor; // 标注分组
q.push(thisNode); // 入队
if (thisColor == 1) // 统计集合中节点的个数
aNode++;
else
bNode++;
};
addOneNode(i, 1); // 先处理这个子图的“源点”
while (q.size()) { // 开始BFS
int thisNode = q.front();
q.pop(); // 队首节点
int toColor = (color[thisNode] == 1 ? 2 : 1); // 它的相邻节点所属的集合
for (int& toNode : a[thisNode]) { // 遍历这个节点的所有边
if (!color[toNode]) { // 相邻节点还未被分组
addOneNode(toNode, toColor); // 处理这个相邻节点(划分集合、入队、统计)
}
else { // 这个相邻节点已经被分组了
if (color[toNode] == color[thisNode]) { // 并且和这个节点还被分到了一组中
puts("0"); // 无法划分为二分图,方案数为0
return 0;
}
}
}
}
ans = (ans * (Pow[aNode] + Pow[bNode])) % mod; // 各个子图的方案数之积
}
}
cout << ans << endl;
return 0;
}
20. 奇妙秘境
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
ll n;
cin >> n;
if (n % 2) {
cout << n * (n - 1) * (n - 2) << endl;
}
else {
if (n % 3 == 0) {
cout << (n - 1) * (n - 2) * (n - 3) << endl;
}
else {
cout << n * (n - 1) * (n - 3) << endl;
}
}
return 0;
}
21. 有趣的平衡
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
int n;
cin >> n;
int k = 1;
while (k <= n) {
k *= 2;
}
int remain = k - n;
cout << 1 << endl;
cout << k << endl;
vector<int> right;
int k2 = 1;
while (k2 < k) {
if (k2 & remain) {
right.push_back(k2);
}
k2 *= 2;
}
cout << right.size() << endl;
for (int i = 0; i < right.size(); i++) {
cout << right[i] << ' ';
}
puts("");
return 0;
}
22. AND
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int a[100010];
int main() {
int n;
cin >> n;
fi (i, 0, n) // for (int i = 0; i < n; i++)
cd(a[i]); // scanf a[i]
ll ans = 0;
for (int i = 0; i < n; i++) {
ll k = a[i];
for (int j = i; j < n; j++) {
k &= a[j];
if (!k)
break; // 剪枝
ans += k;
}
}
cout << ans << endl;
return 0;
}
总结
如上,为本周习题小结,题目内容很简单,还望各位算法大佬见谅,另,其中有部分题解参考了网上的标程与解析,如有侵权,请私信我,看到后立删,谢谢!!!