A. Kyoya and Colored Balls

大意: 给定$k$种颜色的球, 第$i$种颜色有$c_i$个, 一个合法的排列方案满足最后一个第$i$种球的下一个球为第$i+1$种球, 求合法方案数.

简单组合, 添加第$i$种时必须在最后放一个$i$, 剩余任意放, 可重组合算下贡献即可.

#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int P = 1e9+7, P2 = 998244353, INF = 0x3f3f3f3f;
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
const int N = 1e6+10;
int n, fac[N], ifac[N];
int C(int n, int m) {
if (m>n) return 0;
int t = (ll)fac[n]*ifac[m]%P*ifac[n-m]%P;
return t;
}
int main() {
fac[0]=ifac[0]=1;
REP(i,1,N-1) fac[i]=(ll)fac[i-1]*i%P;
ifac[N-1] = inv(fac[N-1]);
PER(i,1,N-2) ifac[i]=(ll)ifac[i+1]*(i+1)%P;
scanf("%d", &n);
int ans = 1, sum = 0;
REP(i,1,n) {
int t;
scanf("%d", &t);
ans = (ll)ans*C(sum+t-1,t-1)%P;
sum += t;
}
printf("%d\n", ans);
}

B. Kyoya and Permutation

大意: 定义了一种对排列的操作, 若一个排列操作后不变则为一个好排列, 求第$k$个好排列.

找下规律发现每个好排列的每个置换大小不超过2, 且大小为2的置换两个数要相邻.

所以可以得到$n$的好排列个数$F(n)$是满足递推$F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)$.

#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std; typedef long long ll;
int n;
ll f[100], k; int main() {
f[0] = 1, f[1] = 1;
REP(i,2,88) f[i]=f[i-1]+f[i-2];
scanf("%d%lld", &n, &k);
REP(i,1,n) {
if (k<=f[n-i]) printf("%d ",i);
else {
k -= f[n-i];
printf("%d %d ", i+1, i);
++i;
}
}
puts("");
}

C. Love Triangles

大意: 给定$n$节点$m$条边无向图, 每条边为0或1, 求补全为完全图, 且任意一个三元环的三条边恰好全1或恰好一个1的方案数.

显然确定两边后第三条边就已经固定了, 所以可以检验出每个连通块是否合法, 假设共cnt个连通块, 答案就是$2^{cnt-1}$.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int N = 1e6+10, P = 1e9+7;
int n, m, ans, vis[N];
struct _ {int to,w;};
vector<_> g[N];
void dfs(int x) {
for (_ e:g[x]) {
if (vis[e.to]==-1) {
vis[e.to] = vis[x]^e.w;
dfs(e.to);
}
else if (vis[e.to]!=(vis[x]^e.w)) ans = 0;
}
}
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].pb({v,!w}),g[v].pb({u,!w});
}
memset(vis,-1,sizeof vis);
ans = (P+1)/2;
REP(i,1,n) if (vis[i]==-1) {
vis[i] = 1, ans = (ll)ans*2%P, dfs(i);
}
printf("%d\n", ans);
}

D Nudist Beach

大意: 给定$n$节点$m$条边无向图, 标记了$k$个点. 要求从未标记的点中选出一个点集$S$, 每个点的价值是$\frac{A}{B}$, $A$为相邻的选中的点, $B$为相邻所有点, 整个点集的价值为所有点价值的最小值. 求$S$价值的最大值.

01分数规划问题, 转为二分答案即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std; const double eps = 1e-8;
const int N = 1e5+10;
int n, m, k;
int deg[N], vis[N], cnt[N], used[N];
vector<int> g[N];
queue<int> q;
int chk(double x) {
REP(i,1,n) cnt[i] = 0;
REP(i,1,n) if (!vis[i]) {
used[i] = 1;
for (int j:g[i]) ++cnt[j];
}
REP(i,1,n) if (cnt[i]<x*deg[i]) q.push(i);
while (q.size()) {
int u = q.front(); q.pop();
if (!used[u]) continue;
used[u] = 0;
for (int v:g[u]) if (--cnt[v]<x*deg[v]) q.push(v);
}
int tot = 0;
REP(i,1,n) tot += used[i];
return tot;
} int main() {
scanf("%d%d%d", &n, &m, &k);
REP(i,1,k) {
int t;
scanf("%d", &t);
vis[t] = 1;
}
REP(i,1,m) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v),g[v].push_back(u);
++deg[u],++deg[v];
}
double l = -eps, r = 1, ans;
REP(i,1,200) {
double mid = (l+r)/2;
if (chk(mid)) ans=mid,l=mid+eps;
else r=mid-eps;
}
chk(ans);
int tot = 0;
REP(i,1,n) tot += used[i];
printf("%d\n", tot);
REP(i,1,n) if (used[i]) printf("%d ", i);
puts("");
}

E.

最新文章

  1. [Javascript]利用当前时间生成yyyymmddhhmmss这样的字符串
  2. Swift 对比学习 (二)
  3. SharePoint 2010 站点附加数据升级到SP2013
  4. IR的评价指标-MAP,NDCG和MRR
  5. 关于Chrome的开发15个小技巧
  6. 针对主流浏览器的CSS-HACK写法及IE常用条件注释
  7. ios中XPath的语法
  8. 获取context path或者basePath
  9. Thinkphp join 连接查询
  10. Atitit。团队建设--管理最佳实践--如何留住关键人才,防止人才外流 ??
  11. iOS开发系统版本适配(未完待续。。。)
  12. .NET DateTime 源码学习
  13. mongodb3.6 (五)net 客户端访问mongodb设置超时时间踩过的“坑”
  14. my first homepage
  15. Visual Studio 2017 最新全量离线下载方法[有惊喜]
  16. web socket client
  17. C++中绝对值的运算
  18. 利用System.Uri转URL为绝对地址
  19. 基于UVM的verilog验证(转)
  20. TensorFlow函数:tf.zeros_like

热门文章

  1. spring事务之事务传播机制和隔离级别
  2. 【零基础】搞定zabbix安装
  3. css实现元素在div底部显示
  4. 获取当前页面的webview ID
  5. Nginx-HTTP之ngx_http_top_body_filter
  6. 阿里云 docker image 加速
  7. tkinter入门-布局方式pack(), grid(), place()
  8. OpenAPI规范入门
  9. MySQL 性能优化系列之一 单表预处理
  10. java+web文件的上传和下载代码