当前位置:首页 >> 学科竞赛 >>

Noip 2013 Day1 解题报告


Noip 2013 Day1 解题报告
--By GreenCloudS

第一题:转圈游戏(快速幂)
根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) mod n) mod n,所以, 只需要求出 10^k mod n 即可, 可以使用快速幂来求解,复杂度 O(log k)。 (

另一个算法,设 f(i)=10^i mod n,则 f(i)=f(i-1)*10 mod n,然后求出 f(i)的循环节,复 杂度 O(n)) 代码(C++):
#include <cstdio> #include <cstring> int k; long long ans; int n,m,x; long long Exp(int y){ if(!y)return 1; if(y==1)return 10%n; if(y&1){ return(((Exp(y>>1)*Exp(y>>1))%n)*10)%n; }else return(Exp(y>>1)*Exp(y>>1))%n; } int main(){ scanf("%d%d%d%d",&n,&m,&k,&x); ans=Exp(k); ans*=m; ans%=n; ans+=x; ans%=n; printf("%lld",ans); return 0; }

第二题:火柴排队(贪心+逆序对)
对距离公式化简得: ∑ (ai-bi)^2= ∑ (ai^2-2aibi+bi^2)= ∑ ai^2+ ∑ bi^2-2 ∑ aibi 要 求 ∑ (ai-bi)^2 最小,就只需要∑aibi 最大即可。这里有个贪心,当 a1<a2<…<an,b1<b2<..<bn 时,∑aibi 最大。证明如下: 若存在 a>b,c>d,且 ac+bd<ad+bc,则 a(c-d)<b(c-d),则 a<b,与 a>b 矛盾,所以若 a>b,c>d,则 ac+bd>ad+bc 将此式子进行推广: 当 a1<a2<a3<...<an ,b1<b2<...<bn 的情况下∑aibi 最大,即∑ (ai-bi)^2 最小。

然后,将两个序列分别排序,确定每对数的对应关系,明显,同 时移动两个序列中的数等效于只移动一个序列中的数,那么,我 们就保持一个序列不动, 然后根据另外那个序列中的数对应的数 的位置,重新定义一个数组,求逆序对个数,就是答案。 例如: 对于数据: 4 2314 3214 先排序:

1234 1234 保持序列 1 不动,那么序列 2 中的 3 就对应序列 1 中的 2 位置, 2 就对应序列 1 中的 1 位置,1 就对应序列 1 中的 3 位置,4 就 对应序列 1 中的 4 位置,那么重定义数组为: 2134 这个序列的逆序对为(2,1),所以答案是 1。

求逆序对方法: 1. 归并排序 2. 把数组扫一遍,顺序把每个数加入 BIT 或者是线段树等数据 结构中,同时查询比这个数大的数有几个,加入答案。 复杂度 : O(n log n)

代码(C++) (树状数组) :
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define MAXN 100010 #define lowbit(x)(((~(x))+1)&x) #define MAX 99999997 struct saver{ int v,t; }; saver a[MAXN],b[MAXN];

bool cmp(saver x,saver y){ return x.v<y.v; } int n,r[MAXN],ans=0; int t[MAXN]; void Add(int x){for(int i=x;i<=n;i+=lowbit(i)) t[i]++;} int Sum(int x){ int rec=0; for(;x;x-=lowbit(x)) rec+=t[x]; return rec; } int main(){ scanf("%d",&n); for(int i=0;i++<n;) scanf("%d",&a[i].v),a[i].t=i; for(int i=0;i++<n;) scanf("%d",&b[i].v),b[i].t=i; sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp); for(int i=0;i++<n;) r[a[i].t]=b[i].t; for(int i=n;i;i--) ans+=Sum(r[i]),Add(r[i]),ans%=MAX; printf("%d\n",ans); return 0; }

第三题: 货车运输 (贪心+最大生成树+树上路径倍增)

首先,我们可以确定贪心的正确性,我们先把边按权值从大到小 排序, 然后依次加入图中, 如果该边的起末点不在同一连通块中, 那么就把边加入,否则不加处理,很明显,这样生成的图,两点 之间要么没有路径,要么唯一一条路径中权值的最小值最大。所

以,我们只要先跑一次最大生成树,然后在求点对之间的树上路 径最小值就可以了。

复杂度:O(m log m + q log n)

代码(C++) (MST+树上倍增) :
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define MAXN 10010 #define MAXM 50010 #define MAXQ 30010 #define MAXD 20 #define clear(x) memset(x,0,sizeof(x)) #define AddEdge(s,t,d) Add(s,t,d),Add(t,s,d) #define inf 0x7fffffff struct saver { int s,t,d; } e[MAXM]; bool cmp(saver x,saver y) { return x.d>y.d; } int father[MAXN],n,m,q,Q[MAXQ][2]; int Find(int x) { int i,j=x; for (i=x;father[i];i=father[i]) ; while (father[j]) { int k=father[j]; father[j]=i; j=k; }

return i; } int up[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN]; bool f[MAXN]; struct edge { edge *next; int t,d; edge () { next=NULL; } } *head[MAXN]; void Add(int s,int t,int d) { edge *p=new(edge); p->t=t,p->d=d,p->next=head[s]; head[s]=p; } void BuildTree(int v) { f[v]=false; for (edge *p=head[v];p;p=p->next) if (f[p->t]) { up[p->t][0]=v,Min[p->t][0]=p->d,h[p->t]=h[v]+1; BuildTree(p->t); } } int Move(int &v,int H) { int rec=inf; for (int i=MAXD-1;i>=0;i--) { if (h[up[v][i]]>=H) { rec=min(rec,Min[v][i]); v=up[v][i]; } } return rec; } int Query(int u,int v) { if (Find(u)!=Find(v)) return -1; int rec=inf; if (h[u]!=h[v]) rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]); // printf("%d\n",rec);

if (u==v) return rec; for (int i=MAXD-1;i>=0;i--) { if (up[u][i]!=up[v][i]) { rec=min(rec,min(Min[u][i],Min[v][i])); u=up[u][i],v=up[v][i]; } } rec=min(rec,min(Min[u][0],Min[v][0])); return rec; } int main() { clear(father),clear(head),clear(up); scanf("%d%d",&n,&m); for (int i=0;i<m;i++) scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].d); sort(e,e+m,cmp); for (int i=0;i<m;i++) if (Find(e[i].s)!=Find(e[i].t)) { father[Find(e[i].s)]=Find(e[i].t); AddEdge(e[i].s,e[i].t,e[i].d); } memset(f,true,sizeof(f)); for (int i=0;i++<n;) if (f[i]) h[i]=0,BuildTree(i),Min[i][0]=inf,up[i][0]=i; for (int i=0;i++<MAXD-1;) { for (int j=0;j++<n;) { up[j][i]=up[up[j][i-1]][i-1]; Min[j][i]=min(Min[j][i-1],Min[up[j][i-1]][i-1]); } } scanf("%d",&q); while (q--) { int u,v; scanf("%d%d",&u,&v); printf("%d\n",Query(u,v)); } return 0; }


相关文章:
Noip 2013 Day1 解题报告
Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...
NOIP2013解题报告
NOIP2013解题报告_计算机软件及应用_IT/计算机_专业资料。NOIP2013解题报告题 计数问题(count.pas/c/cpp) 题目大意: 给出两个数n,x,让你求1...n之间的...
CCF NOIP2013 解题报告&心得
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 CCF NOIP2013 解题报告&心得虽然已经过去很久了, 但是终于有机会有时间写一下解题 报告 ——By 黄锦松 FJ-...
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解_学科竞赛_初中教育_...时间复杂度小于(数的个数*每个数位数), 1 千万以内 的运算次数是肯定不会...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(...(s,9,2),day2); val(copy(s,12,2),hour2); val(copy(s,15,2),...
Noip_2013_提高组_Day2_解题报告
Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二题:花匠(动态规划) 1.令 S[i][1]表示以 i 为结尾, 且降序到达 a[i]的最长...
Noip 2013 提高组 Day2 解题报告
Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛 (模拟)直接贪心...令 h[0]=0,答案就是:∑h[i]-h[i-1](0<i<=n,h[i]>h[i-1]) ...
Noip 2013 解题报告与参赛总结(PASCAL版)
Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013...program ss;(day2t2) const dx:array[1..4]of -1..1=(0,1,-1,0);...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_韩语学习_外语学习_教育专区。NOIP2013复赛模拟8解题报告 NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟...
NOIP2011提高组解题报告day1
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告...Noip 2013 Day1 解题报告... 8页 免费 2003提高组,解题报告 15页 免费 noip...
更多相关标签:
noip2013解题报告 | noip2013day1 | noip2013提高组day1 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2016复赛解题报告 | noip2014解题报告 |