2020 CCPC Wannafly Winter Camp Day 3 (일부 문제)

이번에 보충해야 할 문제가 아주 많아서......구덩이를 남겼다.

7-1 3A. 검은 풍선

팀원들이 아무렇게나 한다고 해서 지나쳤어요. 어떻게 썼는지 잘 못 들었는데 건강 코드로 해요.

#include
#include
#include
#include
#include
#include
#define LL long long
#define inf 0x3f3f3f3f
#define test freopen("in","r",stdin);freopen("out","w",stdout);
#define PII pair
#define PLI pair
using namespace std;
int n;
const int maxn=1e3+5;
int mp[maxn][maxn];
int a[maxn];
int main()
{
    //test
    scanf("%d",&n);
    LL sum=0;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&mp[i][j]),sum+=mp[i][j];
    if(n==2) 
    {
        printf("1 1
");
        return 0;
    }
    sum/=(2*n-2);
    for(int i=1;i<=n;++i)
    {
        LL s=0;
        for(int j=1;j<=n;++j)
        {
            s+=mp[i][j];
        }
        printf("%lld%c",(s-sum)/(n-2)," 
"[i==n]);
    }
    return 0;
}

7-3 3C. 무방향도 방향

독립집을 점으로 축소한 후 문제를 완전도에 대한 방향으로 바꾸어 DAG의 최장로가 얼마나 짧은지를 구한다.답은 결점수래요.똑똑히 생각하지 않아 구덩이를 남겼다

7-5 3E. 장기 형

다른 검은 점에 의해 제어되지 않는 검은 점(A)은 반드시 한 번 눌러진다. 그러면 이 검은 점이 제어하는 검은 점은 A를 누르기 전에 한 구역이 바뀌어도 A를 눌렀을 때 그 구역과 제어된 구역은 다시 원상태로 돌아간다.그래서 우리는 통제되지 않는 검은 점을 누르는 과정을 시뮬레이션하고 몇 걸음 조작했는지 기록하면 된다.2D 차분을 사용하여 영역에 1을 더하는 동작을 시뮬레이션합니다.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const int maxn = 505;
int a[maxn][maxn];
int d[maxn][maxn];
char s[maxn];
int n, m;
int main()
{
    int T;cin>>T;

    while(T--){
        scanf("%d%d", &n, &m);
        memset(d, 0, sizeof d);
        for(int i = 1; i <= n; ++i){
            scanf("%s", s+1);
            for(int j = 1; j <= m; ++j){
                if(s[j] == '0') a[i][j] = 0;
                else a[i][j] = 1;
                //cout< 0; --i){
            for(int j = m; j > 0; --j){
                d[i][j] += d[i+1][j]+d[i][j+1]-d[i+1][j+1];

                if((a[i][j] + d[i][j])%2 == 1){

                    d[i][j]++;
                    ans++;
                }

            }
        }
        if(ans&1) cout<

7-7 3G. 화산이 세계를 주유하다

만약 뿌리가 정해져 있다면 답은 모든 관건과 뿌리로 구성된 자수의 변수*2 - 최장로와 같다.이 두 물건을 교환dp로 유지할 수 있습니다.꽤 고전적인 모형.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define P pair
using namespace std;
const int maxn = 5e5 + 50;
int n, k;
vector
 g[maxn];
int vis[maxn];
int sz[maxn];
ll sum[maxn];
ll first[maxn], second[maxn];
void update(ll x, int id){
    if(x >= first[id]) second[id] = first[id], first[id] = x;
    else if(x > second[id]) second[id] = x;
    return;
}
void dfs(int u, int f){
    if(vis[u]) sz[u]++;
    sum[u] = 0;
    first[u] = second[u] = 0;
    for(int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first;
        ll w = g[u][i].second;
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
        sum[u] += sum[v] + (sz[v]!=0)*2*w;
        ll t = first[v] + (sz[v]!=0)*w;
        //cout<= first[u]) second[u] = first[u], first[u] = t;
//        else if(t > second[u]) second[u] = t;
    }
    //cout<>n>>k;
    for(int i = 1; i < n; ++i){
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u].push_back(P(v, w));
        g[v].push_back(P(u, w));
    }
    while(k--){
        int x; scanf("%d", &x); vis[x] = 1;
    }
    dfs(1, 0);
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; ++i){
        ll ans = sum[i]-first[i];
        printf("%lld
", ans);
    }
}

Day2 문제 하나도 못 붙였어요. 동생 QAQ입니다.