牛客网提高组Day2
T1 方差
第一眼看就知道要打暴力啊,然而并没有想到去化简式子。。。
可能因为昨晚没睡好,今天上午困死
导致暴力打了一个半小时,还不对。。。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int M = ;
int n, m;
double sum;
LL a[M], s[M], f[M]; double mul(double a, int b) {
double res = 0.0;
while (b) {
if (b & ) res += a;
a += a;
b >>= ;
}
return ;
} int main() {
scanf("%d", &n);
m = n - ;
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = ; i <= n; i++) {
if (f[a[i]] != ) {
if(i != n) printf("%lld ", f[a[i]]);
else return printf("%lld\n", f[a[i]]), ;
continue;
}
double tmp = 1.0 * (sum - a[i]) / m;
double ss;
for (int j = ; j <= n; j++) {
if (i == j) continue;
double t = abs(a[j] - tmp);
t = 1.0 * t * t;
ss += t;
}
f[a[i]] = mul(ss, m);
if(i != n) printf("%lld ", f[a[i]]);
else printf("%lld\n", f[a[i]]);
}
return ;
}
假的暴力
正解:
题中公式可进行化简,转化为只需维护序列元素的和,平方和即可
#include<iostream>
#include<cstdio>
using namespace std;
const int M = ;
int n;
long long s, s2, ans;
long long a[M]; int main() {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
s += a[i];
s2 += a[i] * a[i];
}
for (int i = ; i <= n; i++) {
ans = (n - ) * (s2 - a[i] * a[i]) - (s - a[i]) * (s - a[i]);
printf("%lld ", ans);
}
return ;
}
T2 分糖果
暴力搜索 然而并没有分 qwq。。。
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int M = ;
int n, ans;
int f[M], a[M], vis[M]; void dfs(int step) {
if(step == n + ) ans++;
else for(int j = ; j <= f[step]; j++) {
if(!vis[j] && step == n && (a[step - ] != j) && a[] != j) {
a[step] = j;
dfs(step + );
}
else if(!vis[j] && (a[step - ] != j) && step != n) {
a[step] = j;
dfs(step + );
}
} } int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++)
scanf("%d", &f[i]);
dfs();
printf("%d\n", ans);
return ;
}
暴力
正解:
暴力复杂度为O(n^2),所以考虑优化:
线段树优化:O(nlogn) 80pts
单调队列优化:O(n) 100pts
#include<bits/stdc++.h>
using namespace std;
const int M = ;
const int P = 1e9 + ;
int n, B[M], A[M];
int dp[M], sum[];
int q[][M], val[][M], l[], r[]; void insert(int f, int x, int s) {
while (l[f] < r[f] && q[f][r[f] - ] >= x) {
r[f]--;
s = (s + val[f][r[f]]) % P;
sum[f] = (sum[f] - 1ll * val[f][r[f]] * q[f][r[f]] % P + P) % P;
}
val[f][r[f]] = s;
q[f][r[f]++] = x;
sum[f] = (sum[f] + 1ll * s * x % P) % P;
s = ;
while (l[ - f] < r[ - f] && q[ - f][r[ - f] - ] >= x) {
r[ - f]--;
s = (s + val[ - f][r[ - f]]) % P;
sum[ - f] = (sum[ - f] - 1ll * val[ - f][r[ - f]] * q[ - f][r[ - f]] % P + P) % P;
}
if (s) {
val[ - f][r[ - f]] = s;
q[ - f][r[ - f]++] = x;
sum[ - f] = (sum[ - f] + 1ll * s * x % P) % P;
}
} int main() {
scanf("%d", &n);
int mi = , ans = ;
for (int i = ; i <= n; i++) {
scanf("%d", &B[i]);
if (B[mi] > B[i])mi = i;
}
int len = ;
for (int i = mi; i <= n; i++) A[++len] = B[i];
for (int i = ; i < mi; i++) A[++len] = B[i];
dp[] = ;
l[] = r[] = l[] = r[] = ;
for (int i = ; i <= n; i++) {
int mi = A[i];
int f = i & ;
insert(i & , A[i], dp[i - ]);
dp[i] = (sum[f] - sum[ - f] + P) % P;
if (i > ) ans = (dp[i] - ans + P) % P;
}
printf("%d\n", ans);
return ;
}
T3 集合划分
直接输出“-1”没有分 差评。。
正解:
#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
using namespace std;
typedef long long li;
const int M = ;
bool fg[M], vst[M], pt[];
int n, m, k, mx, a[];
int h, t, ft, st[];
int q[M], f[M], tj[M], lst[M];
int as[M];
li s1 = , s2 = ;
li s3 = , srd; li read() {
li x = , y = , c = gc;
while (!isdigit(c)) y = c, c = gc;
while (isdigit(c)) x = (x << ) + (x << ) + (c ^ ''), c = gc;
return y == '-' ? -x : x;
} void print(li q) {
if (q < ) {
pc('-');
q = -q;
}
if (q >= ) print(q / );
pc(q % + '');
} li rd() {
return srd = (srd * s1 + s2 + rand()) % s3;
} int main() {
srand(time());
rd();
int i, j, l;
n = read(); m = read(); k = read();
mx = ( << n) - ;
for (i = ; i <= m; ++i)
a[i] = read(), f[a[i]] = a[i];
if (m > k) return puts("-1"), ;
for (i = ; i <= mx; ++i)
tj[i] = tj[i >> ] + (i & );
for (i = ; i <= mx; i <<= )
for (j = ; j <= mx; j += (i << ))
for (l = j; l < j + i; ++l)
f[l + i] |= f[l];
int q1 = , q2 = ;
for (i = ; i <= mx; ++i) fg[i] = ;
for (i = ; i <= n; ++i) {
if (k & ( << n - i)) ++q1;
else ++q2;
for (j = ; j <= mx; ++j)
if (n - tj[j] == q1 && tj[j] - tj[f[j]] < q2)
fg[j] = ;
}
if (!fg[mx]) {
puts("-1");
return ;
}
int nw, nxt;
q[++t] = mx;
vst[mx] = ;
while (h < t) {
nw = q[++h];
for (i = ; i <= n; ++i)
if (nw & ( << i - )) {
nxt = nw ^ ( << i - );
if (!fg[nxt] || vst[nxt]) continue;
vst[nxt] = ;
lst[nxt] = nw;
q[++t] = nxt;
} }
if (!vst[]) {
puts("-1");
return ;
}
for (nw = ; nw != mx; nw = lst[nw])
st[++ft] = nw;
st[++ft] = mx;
for (i = ; i <= n; ++i) {
if (k & ( << n - i)) {
while (pt[ft - ]) --ft;
nw = st[ft] ^ st[ft - ];
--ft;
for (j = ; j <= mx; ++j)
if (!as[j] && (j & nw)) as[j] = ;
}
else {
l = ;
for (j = ; j <= m; ++j)
if (!as[a[j]]) l |= a[j];
for (j = ; j < ft; ++j)
if (!pt[j] && ((st[j] ^ st[j + ]) & l) == ) {
nw = st[j] ^ st[j + ];
pt[j] = ;
break;
}
for (j = ; j <= mx; ++j)
if (!as[j] && (j & nw)) as[j] = ;
}
}
for(i = ; i <= mx; ++i)
pc(as[i] - + '');
pc('\n');
return ;
}
18/9/16牛客网提高组Day2的更多相关文章
-
18/9/9牛客网提高组Day1
牛客网提高组Day1 T1 中位数 这好像是主席树??听说过,不会啊... 最后只打了个暴力,可能是n2logn? 只过了前30% qwq #include<algorithm> #in ...
-
牛客网 提高组第8周 T1 染色
染色 链接: https://ac.nowcoder.com/acm/contest/176/A 来源:牛客网 题目描述 \(\tt{fizzydavid}\)和\(\tt{leo}\)有\(n\)个 ...
-
牛客网 提高组第8周 T2 推箱子 解题报告
推箱子 链接: https://ac.nowcoder.com/acm/contest/176/B 来源:牛客网 题目描述 在平面上有\(n\)个箱子,每个箱子都可以看成一个矩形,两条边都和坐标轴平行 ...
-
nowcoder(牛客网)提高组模拟赛第一场 解题报告
T1 中位数(二分) 这个题是一个二分(听说是上周atcoder beginner contest的D题???) 我们可以开一个数组b存a,sort然后二分b进行check(从后往前直接遍历check ...
-
nowcoder(牛客网)提高组模拟赛第四场 解题报告
T1 动态点分治 就是模拟..... 但是没有过!! 看了题解之后发现.... 坑点:有可能 \(x<=r\),但是
-
牛客网提高组模拟赛第七场 T3 洞穴(附bitset介绍)
就是DP. 我们可以很简单的想到要枚举中间点,进行边数的转移. 但是因为边长数据范围很大,所以我们考虑log的倍增. 状态设计为\(dp[i][j][k]\),为从节点\(i\)走\(2^k\)步能否 ...
-
牛客网提高组模拟赛第七场 T2 随机生成树
其实看懂题就很水啦qwq,就是求\(1-N\)的约数啦. 暴力求的话时间复杂度是\(O(NlogN)\)的,其实正解是枚举每个数的倍数......这样的时间复杂度是\(\frac{N}{1}+\fra ...
-
牛客网提高组模拟赛第五场 T1同余方程(异或)(位运算)
区间不好做,但是我们可以转化成前缀来做.转化为前缀之后之后就是二维前缀和. 但是我还是不怎么会做.所以只能去看吉老师的题解 (确定写的那么简单真的是题解???). 我们要求模一个数余0,就等于找它的倍 ...
-
牛客网提高组第二场---solution
T1 方差 根据题目要求将式子先写出来注意下面式子中的 $n$ 全部都是 $n-1$$$\begin{aligned}ans&=n^2\times \frac{1}{n}\times \sum ...
随机推荐
-
9.30notes
memcached 缓存机制,减轻数据库负载.它通过在内存中缓存数据和对象来减少读取数据库的次数,从而提高动态.数据库驱动网站的速度. array_slice(data['list'],0,10) ...
-
Math
Math.sin(t) // sin(t) Math.power(x,2*i) // x的2i次方 (double)(Math.round(sum*1000000))/1000000; / ...
-
2016HUAS_ACM暑假集训2G - Who&#39;s in the Middle
这个题真的没什么好说的.一个排序就能解决的问题.唯一感到不爽的是这道题不是0msAC的,希望各位大神能够给我点指导. 头文件#include<algorithm>,注意一下排序函数的用法就 ...
-
Lintcode: Maximum Subarray Difference
Given an array with integers. Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is ...
-
Python基础篇-day3
主要内容:字典 集合 文件处理 字符编码 1.字典dict简介dict就是key value值,索引有意义,数据无序 key定义规则:a:不可变--数字.字符串.元组(可变--列表.字典)b:不能重复 ...
-
netcat工具的使用
用途:网络管理工具. 可以读,写TCP或UDP 网络连接.简写为:nc 常见参数: -h 帮助信息 -l 坚挺模式 -n 指定IP地址 -p 指定端口号 -v 详细输出 1 客户端:很容易建立一个客 ...
-
【转】Django中的request与response对象
关于request与response 前面几个 Sections 介绍了关于 Django 请求(Request)处理的流程分析,我们也了解到,Django 是围绕着 Request 与 Respon ...
-
[刷题]算法竞赛入门经典(第2版) 4-1/UVa1589 - Xiangqi
书上具体所有题目:http://pan.baidu.com/s/1hssH0KO 代码:(Accepted,0 ms) //UVa1589 #include<iostream> #incl ...
-
iOS-FMDB事务【批量更新数据】
打开数据库(sqlite) ///打开数据库 + (BOOL)openDataBase{ _TYDatabase = [[FMDatabase alloc]initWithPath:[self dat ...
-
LeetCode--005--最长回文子串(java)
给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为 1000. 示例 1: 输入: "babad" 输出: "bab" 注意: &qu ...