A -- simple math problem
Time Limit：2s Memory Limit：128MByte
Submissions：1599Solved：270
这个题解是官方写法，官方代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mo=1e9+;
int pow(int a,int b,int c){int ret=;for(;b;b>>=,a=1LL*a*a%c)if(b&)ret=1LL*ret*a%c;return ret;} int p[], q[]; int work(int n){
int t = ;
for(int i = ;i <= ;i ++) if(n >= q[i]) t = i;
return n + t;
} int gr(){
return (rand() << ) + rand();
} int main(){
p[] = ;
int t = ;
for(int i = ;i <= ;i ++) p[i] = p[i - ] * , q[i] = p[i] + - i;
int n;
while(scanf("%d", &n) != EOF) printf("%d\n", work(n));
return ;
}
这题我Wa了八发过了，和官方解法不同，怎么做呢？
一看就觉得肯定是规律题吧，打个表先？于是确实发现了一波规律，结论如下：
输入的这个数如果小于等于10，输出这个数
否则输入这个数加(位数减1)>=pow(10,t),其中t表示这个数的位数，大于输出结果为这个数+位数，否则输出这个数+(位数-1)
下面给出AC代码：(多组输入)
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
while(cin>>n)
{
if(n>=&&n<=)
cout<<n<<endl;
else
{
int ans=,t=;
int m=n;
while(m)
{
m/=;
t++;
}
if((n+t-)>pow(,t))
cout<<n+t<<endl;
else
cout<<n+t-<<endl;
}
}
return ;
}
B -- Buildings
Time Limit：2s Memory Limit：128MByte
Submissions：682Solved：178
题目链接：http://www.ifrog.cc/acm/problem/1149
分析：
下面给出AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; #define N 200010 int n, K, a[N], lg[N], f[][N], g[][N]; int ask(int l, int r){
int k = lg[r - l + ];
return max(f[k][l], f[k][r - ( << k) + ]) - min(g[k][l], g[k][r - ( << k) + ]);
} int main(){
// freopen("1.in", "r", stdin);
scanf("%d%d", &n, &K);
for(int i = ;i <= n;i ++) if(i & (i - )) lg[i] = lg[i - ]; else lg[i] = lg[i - ] + ;
for(int i = ;i <= n;i ++) scanf("%d", &a[i]), f[][i] = g[][i] = a[i];
for(int i = ;( << i) <= n;i ++){
for(int j = ;j + ( << i) - <= n;j ++){
f[i][j] = max(f[i - ][j], f[i - ][j + ( << (i - ))]);
g[i][j] = min(g[i - ][j], g[i - ][j + ( << (i - ))]);
}
}
long long ans = ;
for(int i = ;i <= n;i ++){
int l = i, r = n, mid;
while(l <= r){
mid = (l + r) >> ;
if(ask(i, mid) <= K) l = mid + ; else r = mid - ;
}
ans += l - i;
}
cout << ans << endl;
return ;
}
C -- Collecting apples
Time Limit：2s Memory Limit：128MByte
Submissions：24Solved：7
题目链接：http://www.ifrog.cc/acm/problem/1150
分析：
下面给出AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; typedef int value_t;
typedef long long calc_t;
const int MaxN = << ;
const value_t mod_base = , mod_exp = ;
const value_t mod_v = (mod_base << mod_exp) + ;
const value_t primitive_root = ;
int epsilon_num;
value_t eps[MaxN], inv_eps[MaxN], inv2, inv[MaxN]; value_t dec(value_t x, value_t v) { x -= v; return x < ? x + mod_v : x; }
value_t inc(value_t x, value_t v) { x += v; return x >= mod_v ? x - mod_v : x; }
value_t pow(value_t x, value_t p){
value_t v = ;
for(; p; p >>= , x = (calc_t)x * x % mod_v)
if(p & ) v = (calc_t)x * v % mod_v;
return v;
} void init_eps(int num){
epsilon_num = num;
value_t base = pow(primitive_root, (mod_v - ) / num);
value_t inv_base = pow(base, mod_v - );
eps[] = inv_eps[] = inv[] = ;
for(int i = ; i < num; ++i)
inv[i] = pow(i, mod_v - );
for(int i = ; i < num; ++i){
eps[i] = (calc_t)eps[i - ] * base % mod_v;
inv_eps[i] = (calc_t)inv_eps[i - ] * inv_base % mod_v;
}
} void transform(int n, value_t *x, value_t *w = eps){
for(int i = , j = ; i != n; ++i){
if(i > j) swap(x[i], x[j]);
for(int l = n >> ; (j ^= l) < l; l >>= );
}
for(int i = ; i <= n; i <<= ){
int m = i >> , t = epsilon_num / i;
for(int j = ; j < n; j += i){
for(int p = , q = ; p != m; ++p, q += t){
value_t z = (calc_t)x[j + m + p] * w[q] % mod_v;
x[j + m + p] = dec(x[j + p], z);
x[j + p] = inc(x[j + p], z);
}
}
}
} void inverse_transform(int n, value_t *x){
transform(n, x, inv_eps);
value_t inv = pow(n, mod_v - );
for(int i = ; i != n; ++i)
x[i] = (calc_t)x[i] * inv % mod_v;
} void polynomial_inverse(int n, value_t *A, value_t *B){
static value_t T[MaxN];
if(n == ){
B[] = pow(A[], mod_v - );
return;
}
int half = (n + ) >> ;
polynomial_inverse(half, A, B);
int p = ;
for(; p < n << ; p <<= );
fill(B + half, B + p, );
transform(p, B);
copy(A, A + n, T);
fill(T + n, T + p, );
transform(p, T);
for(int i = ; i != p; ++i)
B[i] = (calc_t)B[i] * dec(, (calc_t)T[i] * B[i] % mod_v) % mod_v;
inverse_transform(p, B);
} void polynomial_logarithm(int n, value_t *A, value_t *B){
static value_t T[MaxN];
int p = ;
for(; p < n << ; p <<= );
polynomial_inverse(n, A, T);
fill(T + n, T + p, );
transform(p, T);
copy(A, A + n, B);
for(int i = ; i < n - ; ++i)
B[i] = (calc_t)B[i + ] * (i + ) % mod_v;
fill(B + n - , B + p, );
transform(p, B);
for(int i = ; i != p; ++i)
B[i] = (calc_t)B[i] * T[i] % mod_v;
inverse_transform(p, B);
for(int i = n - ; i; --i)
B[i] = (calc_t)B[i - ] * inv[i] % mod_v;
B[] = ;
} void polynomial_exponent(int n, value_t *A, value_t *B)
{
static value_t T[MaxN];
if(n == ){
B[] = ;
return;
}
int p = ;
for(; p < n << ; p <<= );
int half = (n + ) >> ;
polynomial_exponent(half, A, B);
fill(B + half, B + p, );
polynomial_logarithm(n, B, T);
for(int i = ; i != n; ++i)
T[i] = dec(A[i], T[i]);
T[] = inc(T[], );
transform(p, T);
transform(p, B);
for(int i = ; i != p; ++i)
B[i] = (calc_t)B[i] * T[i] % mod_v;
inverse_transform(p, B);
} value_t tmp[MaxN];
value_t A[MaxN], B[MaxN], C[MaxN], T[MaxN]; int main(){
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
int n, m, nn, xx, yy;
scanf("%d%d", &nn, &n);
for(int i = ;i <= n;i ++) tmp[i] = ;
for(int i = ;i <= nn;i ++) scanf("%d%d", &xx, &yy), tmp[yy] += xx;
inv2 = mod_v - mod_v / ;
int p = ;
for(; p < (n + ) << ; p <<= );
init_eps(p);
for(int j = ;j <= n;j ++){
for(int i = ;i * j <= n;i ++)
if(j & ) A[i * j] = (A[i * j] + 1LL * inv[j] * tmp[i]) % mod_v;
else A[i * j] = ((A[i * j] - 1LL * inv[j] * tmp[i]) % mod_v + mod_v) % mod_v;
}
polynomial_exponent(n + , A, B);
for(int i = ; i <= n;i ++) printf("%d\n", (B[i] + mod_v) % mod_v);
return ;
}
D -- Delivering parcels
Time Limit：2s Memory Limit：128MByte
Submissions：114Solved：16
题目链接：http://www.ifrog.cc/acm/problem/1151
分析：
下面给出AC代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}
#define SZ 666666
int n,w[SZ],v[SZ];
ll ans=1e18;
pii ps[SZ];
int hm[SZ];
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtt;
rbtt rbt;
void case1(int A,int B)
{
rbt.clear();
int r=n-,g=;
for(int i=;i<=n+n;++i)
if(i!=A&&i!=B) ps[++g]=pii(w[i],v[i]);
sort(ps+,ps++g); hm[g+]=-1e9;
for(int i=g;i>=;--i)
hm[i]=max(hm[i+],ps[i].se);
for(int i=;i<=g;++i)
{
rbt.insert(ps[i].se);
if(g-i>r) continue;
int cur=hm[i+],rm=r-(g-i);
if(rm) cur=max(cur,*rbt.find_by_order(rm-));
ans=min(ans,(ll)max(w[B],ps[i].fi)*v[B]+(ll)w[A]*max(cur,v[A]));
}
}
void case2(int A,int B)
{
rbt.clear();
int g=;
for(int i=;i<=n+n;++i)
if(i!=A&&i!=B) ps[++g]=pii(w[i],v[i]);
sort(ps+,ps++g);
int pp=,p2=;
for(int i=;i<=g;++i)
{
rbt.insert(ps[i].se);
if(rbt.size()<n) continue;
int cur=*rbt.find_by_order(n-);
ans=min(ans,(ll)w[A]*v[B]+(ll)ps[i].fi*cur);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n+n;++i)
scanf("%d",w+i);
for(int i=;i<=n+n;++i)
scanf("%d",v+i);
if(n==)
{
printf("%lld\n",w[]*(ll)v[]+w[]*(ll)v[]);
return ;
}
pii m1(-1e9,-1e9),m2(-1e9,-1e9);
for(int i=;i<=n+n;++i)
m1=max(m1,pii(w[i],i)),
m2=max(m2,pii(v[i],i));
int A=m1.se,B=m2.se;
if(A!=B) case1(A,B);
case2(A,B);
printf("%lld\n",ans);
}
E -- Expected value of the expression
Time Limit：2s Memory Limit：128MByte
Submissions：119Solved：56
题目链接：http://www.ifrog.cc/acm/problem/1152
分析：
下面给出AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; char op[][];
double f[][], p[];
int a[];
int n; int main(){
scanf("%d", &n);
n ++;
for(int i = ;i <= n;i ++) scanf("%d", &a[i]);
for(int i = ;i <= n;i ++) scanf("%s", op[i]);
for(int i = ;i <= n;i ++) scanf("%lf", &p[i]);
double ans = ;
for(int j = ;j < ;j ++){
for(int i = ;i <= n;i ++){
int v = (a[i] >> j) & ;
f[][i] = f[][i] = 0.0;
if(i == ){
f[v][] = ;
f[v ^ ][] = ;
}else{
if(op[i][] == '&'){
f[][i] += f[][i - ] * p[i];
f[][i] += f[][i - ] * p[i];
f[ & v][i] += f[][i - ] * ( - p[i]);
f[ & v][i] += f[][i - ] * ( - p[i]);
}
if(op[i][] == '|'){
f[][i] += f[][i - ] * p[i];
f[][i] += f[][i - ] * p[i];
f[ | v][i] += f[][i - ] * ( - p[i]);
f[ | v][i] += f[][i - ] * ( - p[i]);
}
if(op[i][] == '^'){
f[][i] += f[][i - ] * p[i];
f[][i] += f[][i - ] * p[i];
f[ ^ v][i] += f[][i - ] * ( - p[i]);
f[ ^ v][i] += f[][i - ] * ( - p[i]);
}
}
}
ans += f[][n] * (double)( << j);
}
printf("%.6lf\n", ans);
return ;
}
“玲珑杯”ACM比赛 Round #19题解&源码【A,规律，B,二分，C,牛顿迭代法，D,平衡树，E,概率dp】的更多相关文章
-
“玲珑杯”ACM比赛 Round #12题解&;源码
我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,日后补上剩余题的题解&源码吧! A ...
-
“玲珑杯”ACM比赛 Round #13 题解&;源码
A 题目链接:http://www.ifrog.cc/acm/problem/1111 分析:容易发现本题就是排序不等式, 将A数组与B数组分别排序之后, 答案即N∑i=1Ai×Bi 此题有坑,反正据 ...
-
“玲珑杯”ACM比赛 Round #19 B -- Buildings （RMQ + 二分）
“玲珑杯”ACM比赛 Round #19 Start Time:2017-07-29 14:00:00 End Time:2017-07-29 16:30:00 Refresh Time:2017-0 ...
-
“玲珑杯”ACM比赛 Round #1 题解
A:DESCRIPTION Eric has an array of integers a1,a2,...,ana1,a2,...,an. Every time, he can choose a co ...
-
lonlifeOJ1152 “玲珑杯”ACM比赛 Round #19 概率DP
E -- Expected value of the expression DESCRIPTION You are given an expression: A0O1A1O2A2⋯OnAnA0O1A1 ...
-
玲珑杯”ACM比赛 Round #19 B 维护单调栈
1149 - Buildings Time Limit:2s Memory Limit:128MByte Submissions:588Solved:151 DESCRIPTION There are ...
-
“玲珑杯”ACM比赛 Round #19
A -- A simple math problem Time Limit:2s Memory Limit:128MByte Submissions:1599Solved:270 DESCRIPTIO ...
-
“玲珑杯”ACM比赛 Round #1
Start Time:2016-08-20 13:00:00 End Time:2016-08-20 18:00:00 Refresh Time:2017-11-12 19:51:52 Public ...
-
“玲珑杯”ACM比赛 Round #18
“玲珑杯”ACM比赛 Round #18 Start Time:2017-07-15 12:00:00 End Time:2017-07-15 15:46:00 A -- 计算几何你瞎暴力 Time ...
随机推荐
-
Hybrid技术的设计与实现（转）
浅谈Hybrid技术的设计与实现 前言 随着移动浪潮的兴起,各种APP层出不穷,极速的业务扩展提升了团队对开发效率的要求,这个时候使用IOS&Andriod开发一个APP似乎成本有点过高了,而 ...
-
ubuntu使用经验整理
===================================================== 清理/boot分区 =================================== ...
-
【GoLang】GoLang 遍历 map、slice、array方法
代码示例: map1 := make(map[string]string) map1["a"] = "AAA" map1["b"] = &q ...
-
poj1243（经典dp）
题目链接:http://poj.org/problem?id=1243 题意:让你猜一个物品的价格,猜低了或者猜高了都会提示你.G,L,表示你有G次机会猜一个数,如果猜错了,G会减少1次,如果你的错误 ...
-
201521123122 《java程序设计》 第四周学习总结
1. 本周学习总结 1.1 尝试使用思维导图总结有关继承的知识点. 1.2 使用常规方法总结其他上课内容. 这个思维导图比较简单,详细内容点击此处 2. 书面作业 注释的应用 使用类的注释与方法的注释 ...
-
nodejs的jekins部署
第一步 gitlab项目仓库给jekins服务器分配一个账号develop权限用于拉取代码. 分支为master. 第二步 jekins配置打包脚本. npm install --registry=h ...
-
.Net NPOI 根据excel模板导出excel、直接生成excel
一.根据Excel模板导出excel 1.导入NPOI.dll 2.DAL中添加类ExportExcel.cs using NPOI.SS.UserModel; using System; usin ...
-
solus 系统 - 更新软件源
清华稳定源sudo eopkg ar Tuna https://mirrors.tuna.tsinghua.edu.cn/solus/shannon/eopkg-index.xml 清华不稳定源sud ...
-
HDU5532 Almost Sorted Array(最长上升子序列 or 瞎搞个做差的数组)
题目链接:点我 题意:给定一个序列,询问是否能删除一个数让它成为非递减或者非递增的序列. 比如说 删除后的序列是1 3 3 5 或者5 3 3 1 或者1 3 5 或者5 3 1 都可以.只要满足删掉 ...
-
Android基础知识之Manifest中的Intent-filter元素
原文:http://android.eoe.cn/topic/android_sdk :指定活动.服务.或者广播接收者能支持的intent的类型.一个意图过滤器声明了其父组件的能力——一个活动或者服务 ...