2018-2019 ACM-ICPC, Asia East Continent Finals D.F.I.L(VP)

专业打假赛

VP情况略，不会的题单独补了

D.Deja vu of … Go Players 题目分析

签到题，直接判断 n , m n,m n,m大小关系即可。

Code

#include 
#define int long long
#define endl 'n'
using namespace std;

const int N = 2e5 + 10;
int a[N];


inline void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1, x = 0; i <= n; i++) cin >> x;
    for(int j = 1, x = 0; j <= m; j++) cin >> x;
    if(n > m) cout << "Non";
    else cout << "Yesn";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

F.Interstellar … Fantasy 题目分析

计算几何，不难发现三点一定共面，因此讨论能否走直线到达即可。不能走直线就走切线+圆弧。

Code

#include 
#define int long long
#define endl 'n'
using namespace std;

const int N = 2e5 + 10;
int a[N];

struct point{
    double x, y, z;
    point() {}
    point(int x, int y, int z): x(x), y(y), z(z) {}
    double square() {
        return x * x + y * y + z * z;
    }
};

point dec(point a, point b){
    return point{a.x - b.x, a.y - b.y, a.z - b.z};
}

inline void solve(){
    point o; cin >> o.x >> o.y >> o.z;
    double r = 0; cin >> r;
    point st, ed;
    cin >> st.x >> st.y >> st.z >> ed.x >> ed.y >> ed.z;
    point dec1 = dec(o, st), dec2 = dec(ed, st), dec3 = dec(o, ed), dec4 = dec(st, ed);
    double res0 = (st.x - ed.x) * (st.x - ed.x) + (st.y - ed.y) * (st.y - ed.y) + (st.z - ed.z) * (st.z - ed.z);
    double res1 = dec1.x * dec2.x + dec1.y * dec2.y + dec1.z * dec2.z;
    double res2 = dec3.x * dec4.x + dec3.y * dec4.y + dec3.z * dec4.z;
    double dis = sqrt(dec4.square());

    if (res0 <= 1e-8 || res1 <= 1e-8 || res2 <= 1e-8) cout << dis << endl;
    else {
        double h = sqrt(dec1.square() - res1 * res1 / dec4.square());
        if (r - h <= 1e-8) cout << dis << endl;
        else {  
            double linea = sqrt(dec1.square() - r * r), lineb = sqrt(dec3.square() - r * r);
            double jue = atan2(sqrt(dec1.square() - h * h), h) + atan2(sqrt((dec3.square() - h * h)), h) - atan2(linea, r) - atan2(lineb, r);
            cout << jue * r + linea + lineb << endl;
        }   
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

I. Misunderstood … Missing 题目分析

假定拥有基础攻击力 A A A和增幅 D D D(初始均为 0 0 0)进行 n n n轮游戏，每轮游戏开始 A → A + D A rightarrow A + D A→A+D，每轮游戏可以选择三个操作中的一种：

• 造成 A + a i A + a_i A+ai​的伤害
• 将 D D D变为 D + b i D + b_i D+bi​
• 将 A A A变为 A + c i A + c_i A+ci​

问 n n n轮游戏结束后能够造成的总最大伤害。

每一次的选择都会对后面的操作构成影响，因此考虑倒着 D P DP DP处理。首先一定可以确定第 n n n轮一定会选择操作 1 1 1，因为其它操作不会再对总伤害造成增益。

同时，因为我们需要记录那些回合进行了攻击，那么我们可以加一维表示攻击回合的下标和：设第 i i i轮选择操作 2 2 2， D → D + b i D rightarrow D + b_i D→D+bi​，那么对第 j j j轮的贡献就是 ( j − i ) ∗ b i (j - i) * b_i (j−i)∗bi​，由此可以计算对 [ i , n ] [i, n] [i,n]的总贡献为 ( s u m − j × i ) × b i (sum - j times i) times b_i (sum−j×i)×bi​。

设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示 [ i , n ] [i, n] [i,n]轮游戏中有 j j j次攻击操作，这些攻击操作所在回合下标和为 k k k时造成的最大伤害，那么可以得到转移方程：
d p [ i ] [ j + 1 ] [ k + i ] = max ⁡ ( d p [ i ] [ j + 1 ] [ k + i ] , d p [ i + 1 ] [ j ] [ k ] + a [ i ] ) d p [ i ] [ j ] [ k ] = max ⁡ ( d p [ i ] [ j ] [ k ] , d p [ i + 1 ] [ j ] [ k ] + ( k − j ∗ i ) ∗ b i ) d p [ i ] [ j ] [ k ] = max ⁡ ( d p [ i ] [ j ] [ k ] , d p [ i + 1 ] [ j ] [ k ] + j ∗ c i ) dp[i][j + 1][k + i] = max(dp[i][j + 1][k + i], dp[i + 1][j][k] + a[i]) \ dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k] + (k - j * i) * b_i) \ dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k] + j * c_i) dp[i][j+1][k+i]=max(dp[i][j+1][k+i],dp[i+1][j][k]+a[i])dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k]+(k−j∗i)∗bi​)dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k]+j∗ci​)
显然空间不太够。于是需要滚动数组压掉第一维。

Code

#include 
#define int long long
#define endl 'n'
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N];
int dp[105][6005];

inline void solve(){
    int n = 0, ans = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = n; i; i--){
        for(int j = n; j >= 0; j--){
            for(int k = (n + 1) * n / 2; k >= 0; k--){
                if(dp[j][k] == -1) continue;
                dp[j + 1][k + i] = max(dp[j + 1][k + i], dp[j][k] + a[i]);
                // dp[j][k] = max(dp[j][k], dp[j][k] + (k - j * i) * b[i]);
                // dp[j][k] = max(dp[j][k], dp[j][k] + j * c[i]);
                dp[j][k] = max({dp[j][k], dp[j][k] + c[i] * j, dp[j][k] + (k - j * i) * b[i]});
            }
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= (n + 1) * n / 2; j++){
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

L.Eventual … Journey 题目分析

给定一堆点，点属于两个集合中的一个。从某点出发可以通过道路到达另外一点，或者通过护照直接传送到同个集合的点。问对所有的点而言到达其他点的步数和。

分类讨论即可，记录点的度。注意要特判度为0的情况，即点自身为单点。尤其注意单点到单点的计算.

Code

#include 
#define int long long
#define endl 'n'
using namespace std;

const int N = 2e5 + 10;
int a[N];
vector  g[N];
int cnt[3], cnt2[3];
inline void solve(){
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(a[u] != a[v]){
            g[u].push_back(v); 
            g[v].push_back(u);
        }
        
    }
    for(int i = 1; i <= n; i++){
        if(g[i].size()) cnt2[a[i]]++;
    }
    if(m==0){
        for(int i=1;i<=n;i++){
            cout<
        int ans = 0;
        if(g[i].size()){
            ans = (cnt[a[i]] - 1) + g[i].size() + 2 * (cnt[1 - a[i]] - g[i].size());
        } else {
            ans = cnt[a[i]] - 1 + 2 * cnt2[1 - a[i]] + 3 * (cnt[1 - a[i]] - cnt2[1 - a[i]]);
        }
        cout << ans << " n"[i == n];
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; 
    //cin >> t;
    while(t--) solve();
    return 0;
}

暑期编程PK赛 得CSDN机械键盘等精美礼品！