題目來(lái)源：2017-2018 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2017)

A.Cakey McCakeFace

#include <bits/stdc++.h> #define pb(x) push_back(x) typedef long long ll; const int maxn = 2000+7; using namespace std; int n,m; ll a[maxn], b[maxn]; map<ll, ll> Ma, Mb, M; ll anst,ans; int main() {scanf("%d%d",&n,&m);for(int i=0;i<n;++i)scanf("%lld",&a[i]),++Ma[a[i]];for(int i=0;i<m;++i)scanf("%lld",&b[i]),++Mb[b[i]];for(auto x1: Ma){for(auto x2: Mb)if(x1.first<=x2.first){M[x2.first-x1.first]+=min(x1.second,x2.second);}}for(auto x: M){if(x.second > anst){anst = x.second;ans = x.first;}}printf("%lld\n",ans);return 0; }

?

C.Macarons

狀壓dp+矩陣快速冪裸題，然而。。。注意到矩陣乘法的復(fù)雜度很高，一個(gè)多余的mod，就會(huì)導(dǎo)致慢2倍以上，會(huì)TLE。。。好吧常數(shù)優(yōu)化，太重要了。。。還發(fā)現(xiàn)結(jié)構(gòu)體里的數(shù)組，開(kāi)太大，會(huì)導(dǎo)致代碼，崩的某名奇妙！！

#include <cstdio> #define rg register #define pb(x) push_back(x) typedef long long ll; inline int readint(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } inline ll readll(){char c=getchar();ll x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } const ll mod = 1000000000; int n; ll m, ans[260][260], ans1[260][260], a[260][260], c[260][260], d[260][260]; inline void dfs(int ss, int s, int x, int t) {if(x>=n){++a[t][ss],a[t][ss]%=mod;return;}if(!(s&(1<<x))){dfs(ss,s|(1<<x),x+1,t);// 1*1dfs(ss,s|(1<<x),x+1,t|(1<<x));// 1*2if(x+1<n&&!(s&(1<<(x+1)))) dfs(ss,s|(1<<x)|(1<<(x+1)),x+2,t);// 2*1}else dfs(ss,s,x+1,t); } inline void mul(ll a[][260], ll b[][260], int n){for(rg int i=0;i<n;++i)for(int j=0;j<n;++j)ans[i][j]=0,c[i][j]=a[i][j],d[i][j]=b[i][j];for(rg int i=0;i<n;++i)for(rg int k=0;k<n;++k)if(c[i][k])for(rg int j=0;j<n;++j)if(d[k][j]){ans[i][j] = (ans[i][j] + (c[i][k]*d[k][j]))%mod;//TLE!!!: ans[i][j] = (ans[i][j] + (c[i][k]*d[k][j])%mod)%mod;}for(rg int i=0;i<n;++i)for(rg int j=0;j<n;++j)a[i][j]=ans[i][j]; } ll L; int main() {n=readint(),m=readll();L = (1<<n);for(int s=0;s<L;++s){ans1[s][s]=1;dfs(s,s,0,0);}while(m != 0) {if(m&1)mul(ans1,a,L);if(ans1[0][0]==0)break;mul(a,a,L); m>>=1;if(ans1[0][0]==0)break;}printf("%lld\n",ans1[0][0]%mod);return 0; }

J.Frosting on the Cake

相當(dāng)于多項(xiàng)式乘法，然而，剛?cè)腴T(mén)fft的我，直接寫(xiě)了fft。。。wa，應(yīng)該是精度被卡，實(shí)際上，可以把三種顏色，直接分開(kāi)算出來(lái)。

K.Blowing Candles

之前一直不會(huì)旋轉(zhuǎn)卡殼，原理不難理解，只是計(jì)算幾何的代碼，感覺(jué)好難寫(xiě)。等寫(xiě)好了再貼出來(lái)吧

?

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9034277.html

總結(jié)

以上是生活随笔為你收集整理的Full_of_Boys训练4总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。