[2015 HIAST Collegiate Programming Contest] 题解(AK)

简单的题或者我队友ac的题目没有写思路,只贴了代码,

自己ac的题目把题意和思路都说了一下,也贴上了代码。

[A - Who is the winner?]

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t;
int a[5],b[5];
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t;t;--t){
  	for(int i=1;i<=3;i++){
  		cin>>a[i];
  	}
  	for(int i=1;i<=3;i++){
  		cin>>b[i];
  	}
  	int st=0;
  	for(int i=1;i<=3;i++){
  		if(a[i]<b[i]){
  			st=1;
  			break;
  		}else if(b[i]<a[i]){
  			st=-1;
  			break;
  		}
  	}
  	if(st==1){
  		cout<<"Player1\n";
  	}else if(st==-1)cout<<"Player2\n";
  	else cout<<"Tie\n";
  }
 	return 0;
}

[B - New Job]

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t,n,m;
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t;t;t--){
  	cin>>n>>m;
  	int now=1,ans=0;
  	while(n){
 			now=min(now,m);
 			if(n<=now){
 				ans++;
 				break;
 			}
 			n-=now;
 			ans++;
  		now*=2;
  	}
  	cout<<ans<<'\n';
  }
 	return 0;
}

[C - Palindrome Again !!]

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int t,n,p;
char s[N];
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>t;
	while(t--){
		cin>>n>>p;
		cin>>s;
		--p;
		if(p>=n/2) p=(n-p-1+n)%n;
		int ret=0,l=inf,r=-inf;
		for(int i=0;i<n/2;i++){
			int cost=(s[i]-s[n-i-1]+26)%26;
			cost=min(cost,26-cost);
			ret+=cost;
			if(cost){
                l=min(l,i);
                r=max(r,i);
			}
		}
		int ans=ret;
		if(ret==0){
			cout<<0<<'\n';
			continue;
		}
		if(p>=r){
			ans+=p-l;
		}else if(p>=l){
			ans+=min(p-l,r-p)+r-l;
		}else{
			ans+=r-p;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

D. Time to go back

题意:

你有\(\mathit n\)个礼物,每个礼物的价格是\(a_i\),你准备给\(\mathit m\)个朋友买礼物,其中\(\mathit k\)个朋友的礼物价格必须大于等于\(\mathit d\)

问你有多少中购买礼物的方案。

思路:

容斥一下,先不考虑那\(\mathit k\)个朋友,一共有\(C(n,m)\)种方案,

我们记\(cnt\)为价格大于等于\(\mathit d\)的礼物个数。

然后减去不合法的方案数,他们是\(\sum_{i=0}^{i=k-1}C(cnt,i)*C(n-cnt,m-i)\)

注意过程中要取模即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const ll mod = 1e9 + 7;
ll fac[maxn], inv[maxn];
void pre()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
    inv[maxn - 1] = powmod(fac[maxn - 1], mod - 2, mod);
    for (int i = maxn - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(int a, int b)
{
    if (b > a || b < 0) return 0;
    return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int a[maxn];
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    pre();
    int t;
    t = readint();
    while (t--)
    {
        int n, m, k, d;
        n = readint();
        m = readint();
        k = readint();
        d = readint();
        repd(i, 1, n)
        {
            a[i] = readint();
        }
        if (m > n)
        {
            printf("0\n");
            continue;
        }
        int cnt = 0;
        repd(i, 1, n)
        {
            if (a[i] >= d)
            {
                cnt++;
            }
        }
        if (cnt < k)
        {
            printf("0\n");
            continue;
        }
        ll ans = C(n, m);
        repd(i, 0, k - 1)
        {
            ans = ans - C(cnt, i) * C(n - cnt, m - i) % mod + mod;
            ans %= mod;
        }
        printf("%lld\n", ans );
    }

    return 0;
}

 

[E - Arrange Teams]

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n,m,t,P;
int vis[11][11],p[11],f[11][11];
int ans;
void dfs(int x,int y,int c,int cnt){
	int res=(n-x)*m+m-y;
	if(res<t-cnt) return;
	if(x==n&&y==m){
		if(cnt==t) ans++;
		return;
	}
	int dx=x,dy=y;
	++dy;
	if(dy==m+1){
		dy=1;
		++dx;
	}
	for(int i=0;i<=t;i++) if(!p[i]){
		if(i==0) dfs(dx,dy,i,cnt);
		else{
			if(vis[f[dx-1][dy]][i]||vis[f[dx][dy-1]][i]) continue;
			f[dx][dy]=i;
			p[i]=1;
			dfs(dx,dy,i,cnt+1);
			f[dx][dy]=0;
			p[i]=0;
		}
	}
}
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>T;
	while(T--){
		memset(vis,0,sizeof(vis));
		ans=0;
		cin>>n>>m>>t;
		cin>>P;
		while(P--){
			int a,b;
			cin>>a>>b;
			vis[a][b]=vis[b][a]=1;
		}
		dfs(1,1,0,0);
		rep(i,1,t){
			f[1][1]=i;
			p[i]=1;
			dfs(1,1,i,1);
			f[1][1]=0;
			p[i]=0;
		}
		if(ans==0) cout<<"impossible\n";
		else cout<<ans<<'\n';
	}
	return 0;
}

F - Contestants Ranking

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n;
string s[3];
string p[110];
int dis[110];
map<string,int>vis;
int tot;
vector<int>g[110];
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>T;
	while(T--){
		cin>>n;
		tot=1;
		vis.clear();
		vis["Ahmad"]=1;
		p[1]="Ahmad";
		queue<int>q;
		q.push(1);
		while(n--){
			cin>>s[0]>>s[1]>>s[2];
			rep(i,0,2) if(!vis.count(s[i])){
				vis[s[i]]=++tot;
				p[tot]=s[i];
			}
			rep(i,0,2) rep(j,0,2) if(i!=j){
				g[vis[s[i]]].pb(vis[s[j]]);
				g[vis[s[j]]].pb(vis[s[i]]);
			}
		}
		rep(i,1,tot) dis[i]=inf;
		dis[1]=0;
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int x:g[u]){
				int cost=1+dis[u];
				if(cost<dis[x]){
					dis[x]=cost;
					q.push(x);
				}
			}
		}
		vector<pair<int,string> >ans;
		for(int i=1;i<=tot;i++){
			ans.pb(mp(dis[i],p[i]));
		}
		sort(ans.begin(), ans.end());
		cout<<sz(ans)<<'\n';
		for(auto it:ans){
			if(it.fi==inf) cout<<it.se<<" "<<"undefined\n";
			else cout<<it.se<<" "<<it.fi<<'\n';
		}
		rep(i,1,tot) g[i].clear();
	}
	return 0;
}

(G) The jar of divisors,

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t,n;
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t;t;t--){
  	cin>>n;
  	if(n==1)cout<<"Bob\n";
  	else cout<<"Alice\n";
  }
 	return 0;
}

H. Special Palindrome

题意:

每组数据给定一个整数\(\mathit n\),让你计算有多少个回文数组\(a_1,a_2,\dots,a_i\)满足:

\(\sum a_j=n\)

且回文的对称轴之前是单调不下降的,对称轴之后是单调不上升的。

思路:

记忆化搜索:

搜索函数:

dfs(int pos, int rm)

\(pos\) 为到了第几个数

\(rm\)为目前还剩下多大的数值。

\(a_i\)为当前搜索中序列中的第\(\mathit i\)个数。

\(a_{pos-1},rm\)条件下对答案的贡献进行记忆化,可以很快地得出答案。

代码:

ll ans;
int a[maxn];
ll dp[300][300];
void dfs(int pos, int rm)
{
    if (rm == 0)
    {
        ans++;
        return ;
    }
    if (dp[a[pos - 1]][rm] != -1)
    {
        ans += dp[a[pos - 1]][rm];
        return ;
    }
    ll res = ans;
    if (rm >= a[pos - 1])
    {
        ans++;
    }
    for (int i = a[pos - 1]; i * 2 <= rm; ++i)
    {
        a[pos] = i;
        dfs(pos + 1, rm - i * 2);
    }
    res = ans - res;
    dp[a[pos - 1]][rm] = res;
}
int main()
{
    // freopen("C:\\code\\output.txt","w",stdout);
    memset(dp, -1, sizeof(dp));
    a[0] = 1;
    int i;
    while (cin >> i)
    {
        if (i == 0)
            break;
        ans = 0ll;
        dfs(1, i);
        cout << ans << '\n';
    }

    return 0;
}

I. Mancala

题意:

对于两行每行\(\mathit n\)个数的数组,每个数都大于等于0.

一次操作为选择一个下方的行中的一个数字\(num\),从他逆时针方向的下一个数字开始每个数加1,逆时针方向走一直加,直到加的个数等于\(num\)

现在给定两行每行\(\mathit n\)个数的数组,以及一个操作的结束位置,

让你恢复这次操作之前的数组,如果不存在这样的数组,就输出不合法。

思路:

观察数据范围:

n(1 ≤ n ≤ 10000)

观察题目时限:

time limit per test 3 seconds

所以可以暴力枚举这次操作的起始位置,然后判断是否合法,时间复杂度\(O(n^2)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n;
int x, y;

ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    int cas = 1;
    while (~scanf("%d %d %d", &n, &x, &y))
    {
        if (n + x + y == 0)
            break;
        printf("Case %d:\n", cas );
        cas++;
        repd(i, 1, n)
        {
            a[i] = readint();
            c[i] = a[i];
        }
        repd(i, 1, n)
        {
            b[i] = readint();
            d[i] = a[i];
        }
        int isok = 1;
        ll add = 0ll;
        ll m;
        if (x == 1)
        {
            m = b[1];
            repd(i, 1, n)
            {
                m = min(m, b[i]);
            }
            add += m * n * 2;
            repd(i, 1, n)
            {
                a[i] -= m;
                b[i] -= m;
                if (a[i] < 0)
                {
                    isok = 0;
                }
            }
            if (isok)
            {
                while (y <= n)
                {
                    a[y]--;
                    y++;
                    add++;
                }
                y = n;
                while (y >= 1)
                {
                    if (b[y] == 0)
                    {
                        break;
                    } else
                    {
                        add++;
                        b[y]--;
                        y--;
                    }
                }
                repd(i, 1, n)
                {
                    if (a[i] < 0)
                    {
                        isok = 0;
                    }
                }
            }
        } else
        {
            isok = 0;
            repd(j, 1, n)
            {
                if (j == 3)
                {
                    j = 3;
                }
                m = b[j];
                int flag = 1;
                repd(i, 1, n)
                {
                    c[i] = a[i] - m;
                    d[i] = b[i] - m;
                    if (c[i] < 0 || d[i] < 0) {
                        flag = 0;
                        break;
                    }
                }
                if (!flag)
                {
                    continue;
                }
                add = m * 2 * n;
                if (j > y)
                {
                    repd(i, j + 1, n)
                    {
                        add++;
                        d[i]--;
                    }
                    repd(i, 1, y)
                    {
                        add++;
                        d[i]--;
                    }
                    repd(i, 1, n)
                    {
                        add++;
                        c[i]--;
                    }
                    repd(i, 1, n)
                    {
                        if (c[i] < 0 || d[i] < 0) {
                            flag = 0;
                            break;
                        }
                    }
                    if (flag)
                    {
                        isok = 1;
                        repd(i, 1, n)
                        {
                            a[i] = c[i];
                            b[i] = d[i];
                        }
                        y = j;
                        break;
                    }
                } else
                {
                    repd(i, j + 1, y)
                    {
                        add++;
                        d[i]--;
                    }
                    repd(i, 1, n)
                    {
                        if (c[i] < 0 || d[i] < 0) {
                            flag = 0;
                            break;
                        }
                    }
                    if (flag)
                    {
                        isok = 1;
                        repd(i, 1, n)
                        {
                            a[i] = c[i];
                            b[i] = d[i];
                        }
                        y = j;
                        break;
                    }
                }
            }
        }
        if (isok)
        {
            b[y] += add;
            repd(i, 1, n)
            {
                printf("%lld%c", a[i], i == n ? '\n' : ' ' );
            }
            repd(i, 1, n)
            {
                printf("%lld%c", b[i], i == n ? '\n' : ' ' );
            }
        } else
        {
            printf("INVALID\n");
        }

    }

    return 0;
}


当然也有\(O(n)\)的解法:

//#pragma comment(linker,"/STACK:16777216") /*16Mb*/
//#pragma comment(linker,"/STACK:33554432") /*32Mb*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <list>
#include <iomanip>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<char, char> PCC;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

int n, r, c;
LL a[2][100000];

int main()
{
    //freopen("in.txt", "r", stdin);
    //ios::sync_with_stdio(false); cin.tie(0);
    //srand(time(0));

    //freopen("rooms.in", "r", stdin)
    //freopen("rooms.out", "w", stdout);

    int tst = 0;
    while (cin >> n >> r >> c)
    {
        if (!n) break;
        tst++;
        cout << "Case " << tst << ":\n";
        LL m = 1000000000;
        FOR (i, 0, 2)
        FOR (j, 0, n)
        {
            cin >> a[i][j];
            m = min(m, a[i][j]);
        }
        FOR (i, 0, 2)
        FOR (j, 0, n)
        {
            a[i][j] -= m - 1;
        }
        m--;
        m *= 2 * n;
        r--; c--;
        bool ok = 1;
        while (true)
        {
            //cout << r<<" "<<c<<" "<<a[r][c]<<endl;
            if (a[r][c] == 0 && r == 1)
            {
                a[r][c] = m;
                break;
            }
            if (a[r][c])
            {

                m++, a[r][c]--;
                if (r == 1) c--;
                else c++;
                if (c == -1) r = c = 0;
                if (c == n)
                {
                    c = n - 1;
                    r++;
                }
            }
            else
            {
                ok = 0;
                break;
            }
        }
        if (!ok) cout << "INVALID\n";
        else
            FOR (i, 0, 2)
        {
            FOR (j, 0, n) cout << a[i][j] << " ";
            cout << "\n";
        }

    }

}

J. Polygons Intersection

题意:

两个凸多边形,求其面积交。

思路:

经典的计算几何模板题

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 100;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/

const int maxisn = 100;
const double eps = 1e-6;
const double pi = acos(-1.0);

int dcmp(double x) {
    if (x > eps) return 1;
    return x < -eps ? -1 : 0;
}

struct Point {
    double x, y;
    Point() {
        x = y = 0;
    }
    Point(double a, double b) {
        x = a, y = b;
    }
    inline Point operator-(const Point &b)const {
        return Point(x - b.x, y - b.y);
    }
    inline Point operator+(const Point &b)const {
        return Point(x + b.x, y + b.y);
    }
    inline double dot(const Point &b)const {
        return x * b.x + y * b.y;
    }
    inline double cross(const Point &b, const Point &c)const {
        return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
    }
};

Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d) {
    double u = a.cross(b, c), v = b.cross(a, d);
    return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}

double PolygonArea(Point p[], int n) {
    if (n < 3) return 0.0;
    double s = p[0].y * (p[n - 1].x - p[1].x);
    p[n] = p[0];
    for (int i = 1; i < n; ++ i)
        s += p[i].y * (p[i - 1].x - p[i + 1].x);
    return fabs(s * 0.5);
}

double CPIA(Point a[], Point b[], int na, int nb) { //ConvexPolygonIntersectArea
    Point p[maxisn], tmp[maxisn];
    int i, j, tn, sflag, eflag;
    a[na] = a[0], b[nb] = b[0];
    memcpy(p, b, sizeof(Point) * (nb + 1));
    for (i = 0; i < na && nb > 2; ++ i) {
        sflag = dcmp(a[i].cross(a[i + 1], p[0]));
        for (j = tn = 0; j < nb; ++ j, sflag = eflag) {
            if (sflag >= 0) tmp[tn ++] = p[j];
            eflag = dcmp(a[i].cross(a[i + 1], p[j + 1]));
            if ((sflag ^ eflag) == -2)
                tmp[tn ++] = LineCross(a[i], a[i + 1], p[j], p[j + 1]);
        }
        memcpy(p, tmp, sizeof(Point) * tn);
        nb = tn, p[nb] = p[0];
    }
    if (nb < 3) return 0.0;
    return PolygonArea(p, nb);
}

double SPIA(Point a[], Point b[], int na, int nb) { //SimplePolygonIntersectArea
    int i, j;
    Point t1[4], t2[4];
    double res = 0, if_clock_t1, if_clock_t2;
    a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0];
    for (i = 2; i < na; ++ i) {
        t1[1] = a[i - 1], t1[2] = a[i];
        if_clock_t1 = dcmp(t1[0].cross(t1[1], t1[2]));
        if (if_clock_t1 < 0) std::swap(t1[1], t1[2]);
        for (j = 2; j < nb; ++ j) {
            t2[1] = b[j - 1], t2[2] = b[j];
            if_clock_t2 = dcmp(t2[0].cross(t2[1], t2[2]));
            if (if_clock_t2 < 0) std::swap(t2[1], t2[2]);
            res += CPIA(t1, t2, 3, 3) * if_clock_t1 * if_clock_t2;
        }
    }
    return fabs(res);
}

Point p1[maxn], p2[maxn];
Point p3[maxn], p4[maxn];
int n, m;
int main() {
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        repd(i, 0, n - 1)
        {
            cin >> p1[i].x >> p1[i].y;
        }
        repd(i, 0, m - 1)
        {
            cin >> p2[i].x >> p2[i].y;
        }
        double ans = SPIA(p1, p2, n, m);
        cout << fixed << setprecision(4) << ans << endl;
    }
    return 0;
}