Codeforces Round #178 (Div. 2)
【摘要】
A. Shaass and Oskols
题意：在n条电线上有不同数量的鸟， Shaass开了m枪，每一枪打的是第xi条电线上的第yi只鸟，然后被打中的这只鸟左边的飞到第i-1条电线上，右边的飞到i+1条电线上，没有落脚点的鸟会飞走。
#include <stdio.h>int a[105]; int main(){ ...
题意：在n条电线上有不同数量的鸟， Shaass开了m枪，每一枪打的是第xi条电线上的第yi只鸟，然后被打中的这只鸟左边的飞到第i-1条电线上，右边的飞到i+1条电线上，没有落脚点的鸟会飞走。
-
#include <stdio.h>
-
int a[105];
-
-
int main()
-
{
-
int n, m, x, y;
-
while (scanf("%d",&n) != EOF)
-
{
-
for (int i = 1; i <= n; i++)
-
scanf("%d",&a[i]);
-
scanf("%d",&m);
-
while (m--)
-
{
-
scanf("%d%d",&x,&y);
-
a[x-1] += (y-1);
-
a[x+1] += (a[x]-y+1);
-
a[x] = 0;
-
}
-
for (int j = 1; j <= n; j++)
-
printf("%d\n",a[j]);
-
}
-
return 0;
-
}
题意：Shaass有n本书。每本书都有厚度t和宽度w，t只能为1或2，然后他想做一个书架，我们可以将一本书放在其他书的上面，如题目中的图，然后尽可能的使他们的总厚度最小，输出最小值。
这道题我不会做，感觉是dp，有点像01背包，和01背包不同的是它的厚度是随着放上面书的书面和宽度而变化的。感觉数据量也不大，我觉得可以用暴力来求解。看了别然的博客，发现此题用暴力会tle，我就不试了。还有记忆化搜索的方法解此题，摘自xieshimao的博客，直接看他解题代码。
-
-
#include<stdio.h>
-
#include<string.h>
-
-
int w[105],t[105],n;
-
int mem[105][205][205];
-
-
int min(int a,int b)
-
{
-
if(a>b)
-
return b;
-
else
-
return a;
-
}
-
-
int dfs(int pos,int thi,int whi)
-
{
-
if(pos==n)
-
return thi;
-
if(mem[pos][thi][whi]!=-1)
-
return mem[pos][thi][whi];
-
if(thi-t[pos]>=whi+w[pos])
-
return mem[pos][thi][whi]=min(dfs(pos+1,thi-t[pos],whi+w[pos]),dfs(pos+1,thi,whi));
-
return mem[pos][thi][whi]=dfs(pos+1,thi,whi);
-
}
-
-
int main()
-
{
-
int i,sum;
-
while(scanf("%d",&n)!=EOF)
-
{
-
memset(mem,-1,sizeof(mem));
-
sum=0;
-
for(i=0;i<n;i++)
-
{
-
scanf("%d%d",&t[i],&w[i]);
-
sum=sum+t[i];
-
}
-
printf("%d\n",dfs(0,sum,0));
-
}
-
return 0;
-
}
以下几题来自haha593572013的博客
蛮有意思的，给你m个位置，现在要从这m个位置往位置的两边扩展，问你把所有的数都扩展到总共有多少种方法。
在两个位置中间的那些数的可能的排列数应该是2^（k-1），因为每次都有两种选择，要么左端点，要么右端点。
然后从所有的间隔中各取出一种排列，a1 a2 a3 b1 b2 b3 c1 c2 c3，现在就是求这个序列的总排列数，要求同类的先后顺序不能变，很容易发现这个其实就是类似于多重集合的排列，ans=n!/(p1!*p2!*p3!) ，然后分子再乘上一个2^(k-1)就好了
-
#include <cstdio>
-
#include <vector>
-
#include <cstring>
-
#include <algorithm>
-
using namespace std;
-
typedef long long lld;
-
const int inf = ~0u>>2;
-
const int mod = 1000000007 ;
-
const int maxn = 1010;
-
int pos[maxn];
-
lld Pow(lld a,lld b) {
-
lld ans = 1;
-
while(b) {
-
if(b&1) ans = ans * a % mod;
-
a = a * a % mod;
-
b >>= 1;
-
}
-
return ans ;
-
}
-
lld fac[maxn],two[maxn];
-
vector<int> rec;
-
void solve(int n) {
-
fac[0] = 1; two[0] = 1;
-
for(int i = 1; i <= 1000; i++) fac[i] = fac[i-1] * i % mod;
-
for(int i = 1; i <= 1000; i++) two[i] = two[i-1] * 2 % mod;
-
int sum = 0;
-
for(int i = 0; i < rec.size(); i++) sum += rec[i];
-
// printf("sum=%d\n",sum);
-
lld ans = fac[sum];
-
for(int i = 0; i < rec.size(); i++) {
-
ans = ans * Pow(fac[rec[i]],mod-2) % mod;
-
}
-
for(int i = 1; i < rec.size()-1;i++) {
-
if(rec[i]>0) ans = ans * two[rec[i]-1] % mod;
-
}
-
printf("%I64d\n",ans);
-
}
-
-
int main() {
-
int n , m;
-
scanf("%d%d",&n,&m);
-
for(int i = 0; i < m; i++) {
-
scanf("%d",&pos[i]);
-
}
-
sort(pos,pos+m);
-
rec.push_back(pos[0]-1);
-
for(int i = 1; i < m ; i++) {
-
rec.push_back(pos[i]-pos[i-1]-1);
-
}
-
rec.push_back(n-pos[m-1]);
-
solve(n);
-
return 0;
-
}
给你一棵树，5000个点，每条边有边权，可以删掉一条边再将这条边换个位置，要保证改变后仍然是树的形状，现在问你所有点对的距离之和最小是多少。
5000个点，马上想到n^2..然后就是暴力枚举去掉每条边 ，剩下的就是两棵树，然后重新连接一条边，稍微想一下，这条边肯定就是将两棵树的重心连起来，所以，接下来的事情就简单了。。。
比赛的时候看错了题，以为边可以修改很多次。。。然后各种YY，不够仔细啊。。。
-
#include <cstdio>
-
#include <vector>
-
#include <cstring>
-
#include <algorithm>
-
using namespace std;
-
const int inf = ~0u>>2;
-
const int mod = 1000000007 ;
-
const int maxn = 5010;
-
int son[maxn] ;
-
long long dp[maxn];
-
int n ;
-
int mp[maxn][maxn];
-
vector<int> edge[maxn];
-
int node;
-
struct Edge{
-
int s,t,w;
-
Edge(){}
-
Edge(int a,int b,int c)
-
{
-
s = a;
-
t = b;
-
w = c;
-
}
-
}in[maxn];
-
int dep[maxn];
-
void dfs(int u,int f) {
-
son[u] = 1;
-
dep[u] = dep[f] + 1;
-
int sz = edge[u].size();
-
for(int i = 0; i < sz; i++) {
-
int v = edge[u][i];
-
if(v==f) continue;
-
dfs(v,u);
-
son[u] += son[v];
-
}
-
}
-
int cen;
-
int S[maxn];
-
void DFS(int u,int f) {
-
S[u] = 1;
-
int sz = edge[u].size();
-
for(int i = 0; i < sz; i++) {
-
int v = edge[u][i];
-
if(v == f || v == node) continue;
-
DFS(v,u);
-
S[u] += S[v];
-
}
-
}
-
long long sum;
-
void dfs1(int u,int f,int rt) {
-
dp[u] = 0;
-
int sz = edge[u].size();
-
for(int i = 0; i < sz; i++) {
-
int v = edge[u][i];
-
if(v == f || v == node) continue;
-
dfs1(v,u,rt);
-
sum += (long long ) S[v] * (S[rt]-S[v]) * mp[u][v];
-
dp[u] += dp[v] + (long long)S[v] * mp[u][v];
-
}
-
}
-
long long Mi;
-
void dfs2(int u,int f,int rt) {
-
if(u==rt) {
-
Mi = min(dp[u],Mi);
-
} else {
-
long long tmp = dp[f] - dp[u] - (long long)S[u] * mp[f][u];
-
dp[u] += (long long)mp[f][u] * (S[rt] - S[u]) + tmp;
-
Mi = min(dp[u],Mi);
-
}
-
int sz = edge[u].size();
-
for(int i = 0; i < sz; i++) {
-
int v = edge[u][i];
-
if(v == f || v == node) continue;
-
dfs2(v,u,rt) ;
-
}
-
}
-
int main() {
-
scanf("%d",&n);
-
int a,b,c;
-
int tot = 0;
-
for(int i=1;i<n;i++) {
-
scanf("%d%d%d",&a,&b,&c);
-
edge[a].push_back(b);
-
edge[b].push_back(a);
-
mp[a][b] = mp[b][a] = c;
-
in[tot++] = Edge(a,b,c);
-
}
-
dfs(1,0);
-
long long INF = (long long)1000000000*(long long)1000000000;
-
long long ans = INF;
-
for(int i=0;i<tot;i++) {
-
int u = in[i].s , v = in[i].t;
-
if(dep[u] > dep[v]) swap(u,v);
-
node = v;
-
-
Mi = INF; sum = 0;
-
DFS(1,0);
-
dfs1(1,0,1);
-
dfs2(1,0,1);
-
-
long long tmp = (long long)(son[1]-son[node])*(son[node])*in[i].w;
-
tmp += Mi * (son[node]) ;
-
tmp += sum;
-
Mi = INF; sum = 0;
-
DFS(node,u);
-
dfs1(node,u,node);
-
dfs2(node,u,node);
-
-
tmp += Mi * (son[1]-son[node]);
-
tmp += sum;
-
if(tmp < ans) ans = tmp;
-
}
-
printf("%I64d\n",ans);
-
return 0;
-
}
文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。
原文链接：xindoo.blog.csdn.net/article/details/8770371
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）