【MIX】算法题解(20200731)

ACW 35. 反转链表

题目链接

题面

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点

解析

链表操作题，可以使用迭代实现或者递归实现

AC代码：迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr, *cur=head;
        while(cur){
            ListNode *post=cur->next;
            cur->next=pre;
            pre=cur;
            cur=post;
        }
        return pre;
    }
};

AC代码：递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *p=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        
        return p;
    }
};

ACW 1453. 移掉K位数字

题目链接

题面

给定一个以字符串表示的非负整数 num，移除这个数中的$k$位数字，使得剩下的数字最小。

解析

运用贪心策略求解

1. 如果字符串是单调递增，那么删除字符串后缀即可
2. 如果非单调递增，则找到逆序对进行删除，如果未达到删除字符上限，则转为1问题处理，如果达到则返回.

AC代码

#include<iostream>
using namespace std;

int main(){
    string num;
    int k;
    cin>>num>>k;
    string ans="0";
    for(int i=0; i<num.size(); ++i){
        while(k && num[i]<ans.back()){
            ans.pop_back(); 
            --k;
        }
        ans+=num[i];
    }
    while(k--) ans.pop_back(); // 如果是递增的情况，则直接弹出最后k位
    int i=0;
    while(i<ans.size() && ans[i]=='0') ++i; // 移除前导0
    if(i==ans.size()) cout<<0<<endl;
    else cout<<ans.substr(i)<<endl;
    return 0;
}

ACW 1454. 异或和是质数的子集数

题目链接

题面

给出$n$个互不相同的正整数。
问存在多少个子集，使得子集中所有数的异或和是质数。
由于答案可能很大，请你输出对 $10^9+7$取模后的结果。

解析

动态规划求解，加入滚动数组优化.
根据数据范围可以知道最大异或和不超过$2^{1}3-1=8191$，可以将题目转化为在指定数组中选出若干元素，异或和为质数，这样本题就是一道背包问题.
定义$f[i][j]$表示使用前$i$个元素，可以得到异或和为$j$的方案数量，考虑第$i$个元素$e_i$，如果不选择第$i$个元素，方案数为$f[i-1][j]$，如果选择第$i$个元素方案数为$f[i-1][j\oplus e_i]$，因此可以得到状态转移方程为
$$f[i][j]=f[i-1][j]+f[i-1][j\oplus e_i]$$
整个转移过程可以使用滚动数组优化，降低空间复杂度.

AC代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=5005;
const int M=8192;
const int mod=1e9+7;

int n, a[N], f[2][M];
int primes[M], cnt=0;
bool vis[M];

// 线性筛找出指定范围内的质数
void Lsieve(){
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<=M; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=M/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    Lsieve();
    memset(f, 0x00, sizeof f);
    f[0][0]=1;
    for(int i=1; i<=n; ++i)
        for(int j=0; j<M; ++j){
            f[i&1][j]=f[i-1 & 1][j];
            if((j^a[i])<M) f[i&1][j]=(f[i&1][j]+f[i-1&1][j^a[i]])%mod;
        }
    
    int ans=0;
    for(int i=2; i<M; ++i)
        if(!vis[i]) ans=(ans+f[n&1][i])%mod;
    
    cout<<ans<<endl;
    return 0;
}

ACW 1455. 招聘

题目链接

题面

某公司招聘，有 $n$ 个人入围，HR在黑板上依次写下 $m$ 个正整数 $A_1,A_2,\dots A_m$，然后这 $n$ 个人围成一个圈，并按照顺时针顺序为他们编号 $0,1,2,\dots n-1$。
录取规则是：
第一轮从 0号的人开始，取用黑板上的第 1 个数字，也就是 $A_1$。
黑板上的数字按次序循环使用，即如果某轮用了第 $k$
个，如果 $k<m$，则下一轮需要用第 $k+1$ 个；如果 $k=m$，则下一轮用第 1个。
每一轮按照黑板上的次序取用到一个数字 $A_x$，淘汰掉从当前轮到的人开始按照顺时针顺序数到的第 $A_x$个人。
下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人，被淘汰的人直接回家，所以不会被后续轮次计数时数到。
经过 $n-1$轮后，剩下的最后 1 人被录取，所以最后被录取的人的编号与 $(n,m,A_1,A_2,\dots A_m)$相关。

解析

约瑟夫环问题，动态规划求解.
定义$f[i][j]$表示剩余$i$个人，选用数字下标为$j$，即$A_j$，最终剩下人的编号($0\sim n-1$)，可以发现$f[i][j]$和$f[i-1][j+1]$之间相差一个$A_j$，因此可以得到转移方程
$$f[i][j]=(f[i-1][j+1]+A_j)\mathrm{m}\mathrm{o}\mathrm{d}n$$

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int N=1005;
int n, m;
int a[N];

int main(){
    int T;
    cin>>T;
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i=0; i<m; ++i) scanf("%d", &a[i]);
        
        int ans=0;
        for(int i=1, j=(n-1)%m; i<n;){
            ++i;
            j=(j+m-1)%m;
            ans=(ans+a[j])%i;
        }
        cout<<ans<<endl;
    }   
    return 0;
}