UOJ Round #1

难度很良心啊!

做出了前两题,第三题看到仙人掌就吓哭了。


【UR #1】缩进优化

就是求

\[\sum_{i=1}^n a_i - (x-1)\sum_{i=1}^n\lfloor \frac{a_i}{x} \rfloor
\]

最小值。

调和级数\(O(nlogn)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 2e6+5, mo = 998244353;
inline int read() {
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;
} int n, a[N], m, s[N];
ll ans = 1e18, sum = 0;
ll cal(int x) { //printf("cal %d\n", x);
int lim = m/x;
ll ans = 0;
for(int i=1; i<=lim; i++) ans += i * (s[(i+1) * x - 1] - s[i * x -1]);
//printf("ans %lld %lld\n", ans, sum - (x-1) * ans);
return sum - (x-1) * ans;
}
int main() {
freopen("in", "r", stdin);
n = read();
for(int i=1; i<=n; i++) a[i] = read(), m = max(m, a[i]), s[a[i]]++, sum += a[i];
for(int i=1; i<=m<<1; i++) s[i] += s[i-1];// printf("%d ", s[i]); puts(" s");
for(int x=1; x<=m; x++) ans = min(ans, cal(x));
printf("%lld\n", ans);
}

【UR #1】外星人

题意:

n序列\(a_i\),对于一个排列,x按顺序分别对他们取模,最后得到y,求\(\mid x-y\mid\)最小值以及对应的排列方案数。

题解:

看到排列,当然想到按某种顺序一个个插入

从小到大插入,\(f[i][j]\)表示前i个一开始数是j,最后得到的最大值和方案数

第i个数要产生影响只能放在开头

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define fir first
#define sec second
const int N = 1005, M = 5005, mo = 998244353;
inline int read() {
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;
} int n, x, a[N];
pair<int, int> f[N][M];
int main() {
freopen("in", "r", stdin);
n = read(); x = read();
for(int i=1; i<=n; i++) a[i] = read();
sort(a+1, a+n+1); for(int j=0; j<=x; j++) f[1][j] = make_pair(j % a[1], 1);
for(int i=2; i<=n; i++)
for(int j=0; j<=x; j++) {
pair<int, int> x(f[i-1][j].fir, (ll) (i-1) * f[i-1][j].sec %mo), y = f[i-1][j % a[i]];
if(x.fir == y.fir) f[i][j] = make_pair(x.fir, (x.sec + y.sec) %mo);
else f[i][j] = max(x, y);
} printf("%d\n%d", f[n][x].fir, f[n][x].sec);
}

【UR #1】跳蚤国王下江南

20分暴力!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define fir first
#define sec second
const int N = 1005, mo = 998244353;
inline int read() {
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;
} int n, m, u, v;
struct edge {int v, ne;} e[N<<2];
int cnt, h[N];
inline void ins(int u, int v) {
e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;
e[++cnt] = (edge) {u, h[v]}; h[v] = cnt;
}
bool vis[N];
int ans[N];
void dfs(int u, int l) {
ans[l] ++;
vis[u] = 1;
for(int i=h[u]; i; i=e[i].ne)
if(!vis[e[i].v]) dfs(e[i].v, l+1);
vis[u] = 0;
}
int main() {
freopen("in", "r", stdin);
n = read(); m = read();
for(int i=1; i<=m; i++) ins(read(), read());
dfs(1, 0);
for(int i=1; i<n; i++) printf("%d\n", ans[i]);
}

最新文章

  1. 二.TimesTen原理及应用场景
  2. 读书笔记:《HTML5开发手册》
  3. wxPython入门练习代码 四
  4. Segmentation
  5. linux 安装apahce的configure: error: APR not found. Please read the documentation解决办法
  6. vmware上的Linux获取uuid
  7. Angular2 - Starter - Component and Component Lifecircle Hooks
  8. Bit Map解析
  9. 基础命名空间:序列化 System.Runtime.Serialization
  10. linux下C/C++,多线程pthread《转载》
  11. Android发展简报
  12. react基于nodejs简单的搭建与开发方法
  13. 201521123045-----《Java程序设计》第3周学习总结
  14. SpringMVC框架(二)注解 (转)
  15. windows 下 配置 github
  16. day03 Python字典dict的增删查改及常用操作
  17. IOC 和DI(转载)
  18. Ionic 入门与实战之第三章:Ionic 项目结构以及路由配置
  19. spring+spring mvc+JdbcTemplate 入门小例子
  20. C宏定义

热门文章

  1. vtkQuadratic创建半球面
  2. &lt;!DOCTYPE&gt;标签的定义与用法
  3. jQuery - 自定义伪类 [:pseudoclass]
  4. Wb应用程序开放原理
  5. POJ 3034 Whac-a-Mole(DP)
  6. 【转】Mysql中的排序规则utf8_unicode_ci、utf8_general_ci的区别总结
  7. JAVA网络编程常见问题
  8. 利用mongodb开发lbs应用实践【转】
  9. Hdu1096
  10. Spring webflux
  11. sass进阶—mixin的使用(浏览器兼容性调整)
  12. Apache为mysql以及自己的项目设置虚拟路径
  13. js左右大小变化
  14. Struts2配合layui多文件上传--下载
  15. saltstack returners
  16. Linux 小知识翻译 - 「虚拟化技术」
  17. Http 服务 简单示例
  18. SSL及其加密通信过程
  19. XSS 跨站脚本攻击 的防御解决方案
  20. 领扣-754 到达终点数字 Reach a Number MD