文章目录
(SWERC 2017)
A Cakey McCakeFace
O(N^2) 求出所有的差值即可，map 存下
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2000+10;
LL a[maxn];
int main(void){
map<LL,int> ma;
int N,M;
LL u;
scanf("%d%d",&N,&M);
for(int i = 1;i <= N; ++i){
scanf("%lld",&a[i]);
// ma[u]++;
}
for(int i =1;i <= M; ++i){
scanf("%lld",&u);
for(int i = 1;i <= N; ++i){
if(u >= a[i]){
ma[u-a[i]]++;
}
}
// ma[u]++;
}
LL num = 0;
LL Min = 0;
for(auto c: ma){
if(c.second > num){
num = c.second;
Min = c.first;
}
}
cout<<Min<<endl;
return 0;
}
C Macaron
题意：
用 1∗2,1∗1 的矩阵覆盖 n∗m 的矩形的方法数, n<=8,M<=1e18
分析:
本题是 1033 骨牌覆盖 V2的扩展, 本题的状态比较麻烦，可以用dfs确定状态 i 之后可以转移的状态 j，其中1代表覆盖，0代表未覆盖
// 矩阵快速幂
// 注意修改maxn 的值，要不然容易T
const int maxn = 260;
int n;
struct Matrix{
int n,m;
Matrix(int nn = 1,int mm = 1):n(nn),m(mm){ memset(a,0,sizeof(a));};
int a[maxn][maxn];
};
void print(const Matrix &a)
{
for(int i = 1;i <= a.n; ++i,cout<<endl)
for(int j= 1;j <= a.m; ++j)
cout<<a.a[i][j]<<" ";
}
Matrix operator*(Matrix a,Matrix b)
{
Matrix c(a.n,b.m);
for(int i = 1;i <= a.n; ++i)
{
for(int j = 1;j <= b.m; ++j)
{
for(int k = 1;k <= a.m; ++k)
{
c.a[i][j] = (1ll*c.a[i][j]+1ll*a.a[i][k] * b.a[k][j])%mod;
}
}
}
// print(c);
return c;
}
// 状态压缩
LL MM[maxn][maxn];
LL N,M;
// a 代表是a的递推，now代表当前行的状态，nxt代表下一行的状态
void dfs(int a,int now,int nxt){
// cout<<a<<endl;
int tmpnow = now,tmpnxt = nxt;
int one[10],two[10];
memset(one,0,sizeof(one));
memset(two,0,sizeof(two));
int cnt = 0;
while(tmpnow > 0){
one[cnt++] = tmpnow&1;
tmpnow >>= 1;
}
bool flag = true;
for(int i = 0;i < N; ++i){
if(!one[i]){
flag = false;
break;
}
}
if((now & NN) == NN){
MM[a][nxt]++;
return ;
}
cnt = 0;
while(tmpnxt > 0){
two[cnt++] = tmpnxt&1;
tmpnxt >>= 1;
}
for(int i = 0;i < N; ++i){
if(!one[i]){
dfs(a,now|(1<<i),nxt);
dfs(a,now|(1<<i),nxt|(1<<i));
if(i + 1 < N&& !one[i+1]){
dfs(a,now|(1<<i)|(1<<(i+1)),nxt);
}
break;
}
}
}
int NN;
Matrix ans(NN,NN);
Matrix B(NN,NN);
void solve(){
B.n = B.m = ans.n = ans.m = NN;
for(int i = 1;i <= NN; ++i){
for(int j = 1;j <= NN; ++j)
{
B.a[i][j] = MM[i-1][j-1];
}
}
for(int i = 1;i <= NN; ++i) ans.a[i][i] = 1;
while(M > 0){
if(M & 1)
ans = ans*B;
B = B*B;
M >>= 1;
}
cout<<ans.a[1][1]<<endl;
}
int main(void)
{
scanf("%lld%lld",&N,&M);
// cout<<N<<" "<<M<<endl;
NN = 1<<N;
// cout<<N<<" "<<NN<<endl;
for(int i = 0;i < NN; ++i){
dfs(i,i,0);
}
solve();
return 0;
}
D Candy Chain
E Ingredients
题意
n种菜，每种菜由其它菜加一种食材组合而成，消耗 w,收获 v 点声望，不由其他菜组合而成的为基础菜 ，生产需要消耗 0 ，收获 0 点声望
每一种菜可能由多条方式合成，使用消耗最小的那一个
问： 消耗最小，得到声望最多是多少
分析
跑最短路，然后背包，最短路建图的时候是单向边，可以自己假设一个超级源点
#include<bits/stdc++.h>
using namespace std;
#define Pb push_back
typedef long long LL;
const LL maxn = 1e6+100;
const LL maxm = 30+3;
// char ar[maxm];
// typedef pair<LL,LL> P;
char dish[maxn];
LL C[maxn],V[maxn];
char ar[maxm],br[maxm];
bool vis[maxn];
LL F[maxn];
typedef pair<int,int> P;
struct Edge{
int u,v,d;
int val;
Edge(int uu,int vv,int dd,int va):u(uu),v(vv),d(dd),val(va){
}
};
struct Dijstra{
#define maxn 123456
#define INF 123456789
int N,M,S,T;
typedef pair<int,int> P;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
// int p[maxn];
void init(){
for(int i = 1;i <= N; ++i) G[i].clear();
edges.clear();
// scanf("%d %d %d %d",&N,&M,&S,&T);
// cout<<N<<M<<S<<T<<endl;
// int u,v,w;
// for(int i = 1;i <= M; ++i){
// scanf("%d %d %d",&u,&v,&w);
// AddEdge(u,v,w);
// AddEdge(v,u,w);
// }
}
void AddEdge(int u,int v,int d,int val){
edges.push_back(Edge(u,v,d,val));
int m = edges.size();
G[u].push_back(m-1);
}
void solve(){
priority_queue<P,vector<P>,greater<P>> Q;
for(int i = 1;i <= N; ++i) d[i] = INF;
// cout<<N<<endl;
d[S] = 0;
memset(done,0,sizeof(done));
Q.push(P(0,S));
while(!Q.empty()){
P x = Q.top(); Q.pop();
int u = x.second;
// cout<<u<<endl;
if(done[u]) continue;
done[u] = true;
for(int i = 0;i < (int)G[u].size(); ++i){
Edge &e = edges[G[u][i]];
if(!done[e.v]&&d[e.v] >= d[u]+e.d){
if(d[e.v] > d[u]+e.d)
d[e.v] = d[u] + e.d,V[e.v] = V[u]+e.val,Q.push(P(d[e.v],e.v));
else if(V[e.v] < V[u]+e.val)
V[e.v] = V[u]+e.val,Q.push(P(d[e.v],e.v));
}
}
}
// printf("%d\n",d[T]);
}
};
Dijstra Dij;
bool deg[maxn];
int main(void){
LL M,N;
scanf("%lld%lld",&M,&N);
map<string,LL> ma;
Dij.init();
LL cnt = 0;
LL a,b;
string s1,s2;
for(LL i = 1;i <= N; ++i){
scanf("%s",dish);
scanf("%s%s",ar,br);
scanf("%lld%lld",&a,&b);
s1 = dish;
s2 = ar;
LL u = ma[s1];
LL v = ma[s2];
if(u == 0)
ma[s1] =++cnt,u = cnt;
if(v == 0)
ma[s2] =++cnt,v = cnt;
// cout<<"v "<<v<<" "<<u<<endl;
Dij.AddEdge(v,u,a,b);
// Dij.AddEdge(u,v,a,b);
deg[u]++;
}
for(LL i = 1;i <= cnt; ++i){
// cout<<deg[i]<<" "<<endl;
if(deg[i] == 0)
Dij.AddEdge(cnt+1,i,0,0);
}
// cout<<cnt<<endl;
Dij.S = cnt+1;
Dij.N = cnt+1;
Dij.solve();
// cout<<cnt<<endl;
// 背包
for(int i = 1;i <= cnt; ++i)
C[i] = Dij.d[i];
for(LL i = 1;i <= cnt; ++i){
// if(V[i] == 0) continue;
for(LL j = M;j >= C[i]; --j){
F[j] = max(F[j],F[j-C[i]]+V[i]);
}
}
// for(int i = 1;i <= cnt; ++i)
// cout<<C[i]<<" "<<V[i]<<endl;
LL idx = 0;
for(LL i = 0;i <= M; ++i){
if(F[M] > F[idx]){
idx = i;
}
}
cout<<F[idx]<<endl;
cout<<idx<<endl;
return 0;
}
F Shattered Cake
面积不变
J Frosting on the Cake
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long LL;
LL A[maxn];
LL sum[4];
LL ans[4];
int main(void){
int n;
scanf("%d",&n);
// LL tmp = 0;
for(int i = 1;i <= n; ++i){
scanf("%lld",&A[i]);
// tmp += A[i];
sum[(i-1)%3+1] += A[i];
}
// cout<<sum[1]<<" "<<sum[2]<<" "<<sum[3]<<endl;
LL u,v;
u = v = 0;
LL ans[10] = {0};
for(int i = 1;i <= n; ++i){
scanf( "%lld",&u);
for(int j = 1;j <= 3; ++j){
ans[(i+j)%3] += sum[j]*u;
}
v = u;
}
cout<<ans[0]<<" "<<ans[1]<<" " <<ans[2]<<endl;
return 0;
}
京公网安备 11010502036488号