2018-2019 ACM-ICPC Pacific Northwest Regional Conteest(Div.1)題解

テーマリンク:転送をクリックしてください.
B.C.oprime Integers
最も入門したモビルウスの再演は、あまりいい話ではないので、入門ブログのモビウスの再演をオススメします.

#include
#define ll long long
using namespace std;
const int maxn = 1e7 + 10;
int vis[maxn], pri[maxn], mu[maxn], cnt;
void init(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n ; i++) {
        if (!vis[i])
            pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; i * pri[j] <= n; j++) {
            vis[pri[j] * i] = 1;
            if (i % pri[j])
                mu[i * pri[j]] = -mu[i];
            else
                break;
        }
    }
    for (int i = 2; i <= n; i++)
        mu[i] += mu[i - 1];
}
ll gao(int n, int m) {
    if (!n || !m)
        return 0;
    ll ans = 0;
    if (n > m)
        swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += 1ll * (mu[r] - mu[l - 1]) * (n / l) * (m / l);
        //printf("ans = %d
", ans);
    }
    return ans;
}
int main () {
    int a, b, c, d;
    init(1e7);
    cin>>a>>b>>c>>d;
    ll ans = 0;
    ans = gao(b, d) - gao(a - 1, d) - gao(b, c - 1) + gao(a - 1, c - 1);
    cout<<ans;
}

C.C.ontest Setting
d[i][j]を前のi種のためにj種の方案数を記録して、私達は一つのmpで各種類の数量を記録します.それでは全部i種の数に対して、私はこの数を取らないとd[i]=d[i-1][j]を取ります.

#include
#define ll long long
using namespace std;
const int mod = 998244353;
ll d[1010][1010];
int a[1010];
map<int, int> mp;
void add(ll &x, ll y) {
    x += y;
    while (x >= mod)
        x -= mod;
}
int main () {
    int n, k;
    cin>>n>>k;
    for (int i = 1; i <= n; i++)
        cin>>a[i], mp[a[i]]++;
    sort(a + 1, a + 1 + n);
    n = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n; i++) {
        d[i - 1][0] = 1;
        for (int j = 1; j <= i; j++) {
            add(d[i][j], d[i - 1][j] + d[i - 1][j - 1] * mp[a[i]] % mod);
        }
    }
    cout<<d[n][k]<<endl;
}

D.C.ount The Bits
f[i][j]を0から2^iのうち%k=jの数の個数とし、d[i][j]を0から2^iのうち%k=jの数のバイナリ1の個数とすると、答えはd[n][0]を求め、f[i]に対しては、最高位で0:f[i]=f[i-1]を取ることができます.最高位取1のバイナリ数は1 XXXXと表現でき、XXXXはd[i-1][j]のすべての情報を記録しています.j=2^i%k+XXXX%k、XXXX%k=j-2^i%kとなります.ok、私達はd配列を移動します.同じ最高位は0、d[i]=d[i-1]、[j]です.最高位は1:d[i]、[j]+=d[i-1][(j-2^i)%k]ですが、まだ何か足りません.最高位の1は計算されていません.明らかにf[i-1][(j-2^i)]、d[i][j]にこれを加えると正しいです.私のコードはスクロール配列を使いました.

#include
#define ll long long
using namespace std;
const int maxn = 1010, mod = 1e9 + 9;
ll d[2][maxn] ,f[130][maxn];
void add(ll &x, ll y) {
    x = (x + y) % mod;
}
int gao(int x) {
    if (!x)
        return 0;
    return gao(x / 2) + (x % 2);
}
int main () {
    int n, k, p = 1, m = 1, s = 1, cur = 0;
    cin>>k>>n;
    for (m = 1; m < k && s < n; m <<= 1)
        p = p * 2 % k, s++;
    for (int i = 0; i < m && (i < (1 << s)); i++) {
        d[cur][i % k] += gao(i);
        f[cur][i % k]++;
    }
    for (int i = s; i <= n; i++) {
        cur = !cur;
        for (int j = 0; j < k; j++) {
            d[cur][j] = d[!cur][j];
            int q = (j - p + k) % k;
            add(d[cur][j], d[!cur][q] + f[!cur][q]);
            f[cur][j] = f[!cur][j];
            add(f[cur][j], f[!cur][q]);
        }
        p = p * 2 % k;
    }
    cout<<d[cur][0];
}

E.C.ops And Roobers
私達は最低のお金を使ってBを邪魔します.Bが境界から出られないようにします.実は最小カットを求めます.各点uを入点u 1、出点u 2、接続u 1–u 2に崩します.流量は無限大で、まずソースS接続B入力点、流量は無限大で、すべての境界点の出点接続点T、この境界点が普通点であれば、流量は無限大にします.さもなくば、タイトルの与えられた権利値として、すべての隣接点u,v,接続u 2–v 1に対して、流量はテーマによって無限大または与えられた権利値を設定して、それから最大ストリームを走ります.

#include
using namespace std;
const int maxn=2010;
const int inf=1e9;
struct Edge
{
	int from,to,cap,flow;
};
struct Dinic
{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vis[maxn];
	int cur[maxn],d[maxn];
	void Addedge(int from,int to,int cap)
	{
		edges.push_back((Edge){from,to,cap,0});
		edges.push_back((Edge){to,from,0,0});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	void init(int n)
	{
		this->n=n;
		edges.clear();
		for(int i=0;i<maxn;i++)
		G[i].clear();
	}
	bool bfs()
	{
		memset(vis,0,sizeof(vis));
		queue<int>Q;
		Q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!Q.empty())
		{
			int x=Q.front();Q.pop();
			for(int i=0;i<G[x].size();i++)
			{
				Edge& e=edges[G[x][i]];
				if(!vis[e.to]&&e.cap>e.flow)
				{
					vis[e.to]=1;
					d[e.to]=d[x]+1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int dfs(int x,int a)
	{
		if(a==0||x==t)return a;
		int flow=0,f;
		for(int& i=cur[x];i<G[x].size();i++)
		{
			Edge& e=edges[G[x][i]];
			if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
			{
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a==0)
				break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t)
	{
		this->s=s,this->t=t;
		int flow=0;
		while(bfs())
		{
			memset(cur,0,sizeof(cur));
			flow+=dfs(s, inf);
		}
		return flow;
	}
}solve;
char s[35][35];
int n, m, c[26];
int id(int i, int j) {
    return (i - 1) * m + j;
}
int gao(int i, int j, int T) {
    int flow = inf;
    if (s[i][j] != '.' && s[i][j] != 'B')
        flow = c[s[i][j] - 'a'];
    if (T && T <= n * m)
        T += n * m;
    solve.Addedge(id(i, j), T, flow);
}
int main()
{
    int k;
    cin>>n>>m>>k;
    swap(n, m);
    int S = 0, T = n * m * 2 + 1;
    solve.init(T + 1);
    for (int i = 1; i <= n; i++)
            cin>>s[i] + 1;
    for (int i = 0; i < k; i++)
        cin>>c[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'B')
                solve.Addedge(S, id(i, j) + n * m, inf);
            int flow = inf;
            if (s[i][j] != '.' && s[i][j] != 'B')
                flow = c[s[i][j] - 'a'];
            solve.Addedge(id(i, j) + n * m, id(i, j), flow);
        }
        gao(i, 1, T);
        if (m != 1)
            gao(i, m, T);
        if (i == 1)
            for (int j = 2; j < m; j++)
                gao(i, j, T);
        else if (i == n)
            for (int j = 2; j < m; j++)
                gao(i, j, T);
    }
    for (int i = 1; i < n; i++)
    for (int j = 1; j < m; j++) {
        gao(i, j, id(i, j + 1));
        gao(i, j, id(i + 1, j));
        gao(i, j + 1, id(i, j));
        gao(i + 1, j, id(i, j));
    }
    int ans = solve.maxflow(S, T);
    if (ans == inf)
        puts("-1");
    else
        cout<<ans;
}

F.Rectangles
競技場に偽のスキャン線が書いてあります.Tは飛んでしまいました.各長方形を二つの辺(上の辺と下の辺)に分けて並べ替えます.そして各辺を列挙します.sum線分樹記録区間は奇数回の線分の総長を更新します.線分樹区間の更新は簡単です.iの両端点を線分樹の中に更新します.このような合法的な区間を見つけます.[l,r]は、この区間の長さがX[r]-X[l-1]であり、この区間を更新し、以前の更新回数が偶数の線分総長が現在の奇数の総長となり、sum[o]=X[r]-X[l-1]-sum[o]を更新し、ans+=(辺i＋1の高さ-辺iの高さ)を、線分樹中の全回数が奇数の総長線分に更新される.

 #include
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
int sum[maxn * 4], tag[maxn * 4];
struct node {
    int l, r, h;
    bool operator<(const node& t) const {
        return h < t.h;
    }
} a[maxn];
int X[maxn];
void up(int o, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) {
        sum[o] = X[r] - X[l - 1] - sum[o];
        tag[o] ^= 1;
        return;
    }
    int m = (l + r) / 2, ls = o * 2, rs = o * 2 + 1;
    if (tag[o]) {
        sum[ls] = X[m] - X[l - 1] - sum[ls];
        sum[rs] = X[r] - X[m] - sum[rs];
        tag[ls] ^= tag[o]; tag[rs] ^= tag[o];
        tag[o] = 0;
    }
    if (ql <= m)
        up(ls, l, m, ql, qr);
    if (qr > m)
        up(rs, m + 1, r, ql, qr);
    sum[o] = sum[ls] + sum[rs];
}
int main() {
    int n, x1, y1, x2, y2, sz = 0;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>x1>>y1>>x2>>y2;
        a[i].l = x1, a[i].r = x2;
        a[i].h = y1;
        a[i + n] = a[i];
        a[i + n].h = y2;
        X[++sz] = x1;
        X[++sz] = x2;
    }
    sort(a + 1, a + 1 + n * 2);
    sort(X + 1, X + 1 + sz);
    sz = unique(X + 1, X + 1 + sz) - X - 1;
    ll ans = 0;
    for (int i = 1; i <= n * 2; i++) {
        int l = lower_bound(X + 1, X + 1 + sz, a[i].l) - X;
        int r = lower_bound(X + 1, X + 1 + sz, a[i].r) - X;
        up(1, 1, sz, l + 1, r);
        if (i < n * 2)
            ans += 1ll * sum[1] * (a[i + 1].h - a[i].h);
    }
    cout<<ans;
}

H.Repeating Goldbachs
まず、線形ふるいまたはオラふるい素数の後、暴力はnを求めるだけでいいです.

#include
#define ll long long
using namespace std;
const int maxn = 1e6 + 10, mod = 1e6 + 10;
int vis[maxn];
void init(int n) {
    for (int i = 2; i <= n; i++)
    if (!vis[i]) {
        for (int j = i * 2; j <= n; j += i)
            vis[j] = 1;
    }
}
int gao(int n) {
    if (n < 4)
        return 0;
    if (n == 4)
        return 1;
    for (int i = 3; ;i++)
        if (!vis[i] && !vis[n - i])
            return gao(n - i - i) + 1;
}
int main () {
    init(1e6);
    int n;
    cin>>n;
    printf("%d
", gao(n));
}