Topcoder SRM 698 题解

D1L1

• 枚举分界点。
• 拆成两个串，然后就是个类似于LCS的DP了。

#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1e9+7;
int dp[102][102];
struct RepeatString {
    int minimalModify(string s) {
        int len = s.length();
        string s1,s2;
        int ans = INF;
        for(int i=0;i<len;i++) {
            // [0,i)[i,len)
            s1 = "?", s2 = "!";
            for(int j=0;j<i;j++)   s1+=s[j];
            for(int j=i;j<len;j++) s2+=s[j];
            
            int len1 = s1.length();
            int len2 = s2.length();
            
            dp[0][0] = 0;
            for(int j=1;j<len1;j++) dp[j][0] = j;
            for(int j=1;j<len2;j++) dp[0][j] = j;
            for(int j=1;j<len1;j++) {
                for(int k=1;k<len2;k++) {
                    dp[j][k] = INF;
                    dp[j][k] = min(dp[j-1][k]+1, dp[j][k]);
                    dp[j][k] = min(dp[j][k-1]+1, dp[j][k]);
                    if (s1[j] == s2[k])
                        dp[j][k] = min(dp[j-1][k-1], dp[j][k]);
                    else
                        dp[j][k] = min(dp[j-1][k-1]+1, dp[j][k]);
                }
            }
            ans = min(ans, dp[len1-1][len2-1]);
        }
        return ans;
    }
} T;

D2L2

• 正难则反，考虑一下不想交的pair有多少个。
• 注意到两个不相交的凸多边形，内公切线条数=2[很神妙的性质]
• 枚举切线即可。

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
typedef long long LL;
LL p[102], c[102][102];
struct IntersectingConvexHull {
    void init() {
        p[0]=1;
        for(int i=1;i<102;i++) p[i]=p[i-1]*2LL%MOD;
        c[0][0]=1; for(int i=1;i<102;i++) c[i][0]=1;
        for(int i=1;i<102;i++)
            for(int j=1;j<=i;j++)
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
    }  

    int count(vector<int> x, vector<int> y) {
        init();
        LL ans = 0;
        int n = x.size();
        for (int i=6;i<=n;i++) {
            for (int j=3;j<=i-3;j++) {
                ans = (ans + c[n][i] * c[i][j] % MOD) % MOD;
            }
        }

        for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++) {
            int up = 0, down = 0;
            for(int k=0;k<n;k++) if (k!=i && k!=j){
                if ( (LL)(x[i]-x[j])*(y[i]-y[k]) < (LL)(y[i]-y[j])*(x[i]-x[k]) )
                    up ++;
                else
                    down ++;
            }   
            //printf("Point (%d,%d)-(%d,%d)\n", x[i],y[i],x[j],y[j]);
            //printf("%d %d (%d*%d)\n", up, down,(p[up] - 1 - up),(p[down] - 1 - down));

            ans = ans - 2 * (p[up] - 1 - up) * (p[down] - 1 - down) % MOD;
            ans = (ans % MOD + MOD) % MOD;  
        }
        cout << ans << endl;
        return ans;
    }
} T;

D1L3

咕咕咕