请勿点开

最近想了很多,ACM究竟要不要参加。
大二参加本就胜算渺茫,加上本也没有很强的能力,几乎去了就是打铁。
再者,专业以后的方向是通信类人工智能,对代码要求不高,即使有了ACM的成绩也只是锦上添花而已。
可是为什么还是想去呢(对,我现在还没去新生队伍,更别提校12345队了)
因为喜欢?就是因为喜欢。
闲着的时候可以做几道题就会心情很好,有人一起做题打比赛也会心情很好,注意力不集中时看看算法也会瞬间集中精力。
这大概是我闲着的时候最想做的事了。
可是
为什么我还需要使劲说服自己,才能鼓起勇气参加ACM呢?
我真的有参加的资格和信心和精力吗.....枯了

2020.09.26

第一次Aliyun天池赛,比赛对小白很友好 2/4 收获优酷VIP月卡一张...

A: K步编辑

题意:给一堆字符串,和目标字符串和可变次数。每次可以增加/删除/替换一个字符,找出哪些可以在k步内变成目标字串的。
思路:最短编辑距离,动态规划。dp[i][j]表示看str1[0,i-1]变成target[0,j-1]需要的步数。

  • 如果str1[i] == str[j], 则不用变, dp[i][j] = dp[i-1][j-1]
  • 反之, dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;

代码在此

class Solution {
public:
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */
    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> v;
        for(int i = 0;i < words.size();i++){
            if(check(words[i],target) <= k) v.push_back(words[i]);
        }
        return v;
    }
    
    int check(string str,string target){
        int n1 = str.size();
        int n2 = target.size();
        if(n1 == 0 || n2 == 0) return max(n1,n2);
        
        int dp[n1+1][n2+1];
        for(int i = 0;i <= n1;i++) dp[i][0] = i;
        for(int i = 0;i <= n2;i++) dp[0][i] = i;
        
        for(int i = 1;i < n1+1;i++){
            for(int j = 1;j < n2 + 1;j ++ ){
                if(str[i-1] == target[j-1]) dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
};

B: 折纸

题意:一张纸从右往左折,凹痕为0,凸痕为1,问折n次后痕迹的01串
思路:找规律(发现都是上一个痕迹的奇数位上的0/1左面添上‘0’,右面添上‘1’)。
举例:第3次(0010010)第4次(001 0 011 0 001 1 001)

代码在此

class Solution {
public:
    /**
     * @param n: The folding times
     * @return: the 01 string
     */
    string getString(int n) {
        // Write your code here
        string s = "0";
        if(n == 1) return s;
        for(int i = 2;i <= n;i++){
            string ans;
            for(int j = 0;j < s.length();j++){
                if(j % 2 == 0){
                    if(s[j] == '0') ans += "001";
                    else ans += "011";
                }
                else ans += s[j];
            }
            s = ans;
        }
        return s;
    }
};

C: 字符串的不同排列

题意:给字符串str[0],求升序且不重复的全排列。
思路:递归,先让整个串中的每一位都有机会作str[0],再继续排列str.length()-1位的字符串,重复上述操作。

代码在此

#include<stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

void swap(string &A,int i,int j){
    char tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

void prim(string &A,int p,int q,vector<string> &ans){
    if(p == q) ans.push_back(A);
    else{
        for(int i=p; i<=q; i++){
        swap(A,i,p);
        prim(A,p+1,q,ans);
        swap(A,i,p);
        }
    }
}

int main()
{
    string str;
    cin >> str;
    vector<string> ans;
    prim(str,0,str.size()-1,ans);
    sort(ans.begin(),ans.end());
    cout<<ans[0]<<endl;
    for(int i = 1;i < ans.size();i++){
        if(ans[i] != ans[i-1])cout<<ans[i]<<endl;
    }
}

D: 硬币排成线

题意:给一串数values[],两个人,每人每次拿走一个数,动手的时候只能从两边拿,问第一个拿的数的总和能不能更大。
思路:动态规划,dp[i][j]表示在 i~j 区间先手的优势。从小变大逐渐看dp[i][j] = max(values[i] - dp[i+1][j] ,values[j] - dp[i][j-1])。注意:在所给数有偶数个或只有1个时必定先手可以更大。

代码在此

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int n = values.size();
        if(n <= 2 || n % 2 == 0) return true;
        vector<vector<int>> dp;
        dp.resize(n,vector<int>(n));
        for(int i = 0;i < n;i++){
            dp[i][i] = values[i];
        }
        for(int i = n-2;i >= 0;i--){
            for(int j = i+1;j < n;j++){
                dp[i][j] = max(values[i] - dp[i+1][j],
                    values[j] - dp[i][j-1]);
            }
        }
        if(dp[0][n-1]>0) return true;
        return false;
    }
};

Last modification:September 26th, 2020 at 02:33 pm
请赏我杯奶茶,让我快乐长肉