noip2009提高组题解
NOIP2009题解
T1:潜伏者
题目大意:给出一段密文和破译后的明文,一个字母对应一个密文字母,要求破译一段密文,如果有矛盾或有未出现密文无法破译输出failed,否则输出明文。
思路:纯模拟题
T2:Hankson的趣味题
题目大意:给出a0,a1,b0,b1求满足条件的x的个数;
条件:gcd(x,a0)=a1;x,b0最小公倍数为b1;
思路:分解质因数,假设对于一个质因数y,a0含有a0c个y,a1含有a1c个y,b0含有b0c个y,b1含有b1c个y。
那么不难得到,如果a0c<a1c,那么就无解;如果a0c=a1c,那么x至少含有a1c个y;如果a0c>a1c,那么x只可能含有a1c个y。
同理,如果b1c<b0c,那么就无解;如果b1c=b0c,那么x至多含有b1c个y;如果b1c>b0c,那么x只可能含有b1c个y。
由此,可以求出对于每一个质数,x可能含有几个它,并求出一共有多少种选择方式。然后根据乘法原理,将每一个质数的选择方案数乘起来,就得到了答案。
----------------------------------------------------------
2017.5.6补充题解:
今天又做了一遍,然后对上面自己的做法一脸懵逼,估计是之前就没看懂吧然后贴了题解???
然后就各种焦虑,物色到了一个超级有道理的题解:
可以证明gcd(x/a1,a0/a1)==1,显然如果不等于1,则gcd(x,a0)<a1;
然后可以证明gcd(b1/x,b1/b0)==1,显然如果不等于1,则lcm(x,b0)<b1;
这样的话,显然就可以枚举b1的所有因数,sqrt(b1),加上gcd复杂度是logb1,所以单组数据复杂度是sqrt(b1)*log2(b1).
T3:最优贸易
题目大意:n个城市m条路,有单向和双向,水晶球在每个城市价格不同,求从城市1到n能获得的最大差价,每个城市可走多次。
思路,边数太多,所以用SPFA,正向做一次取最小,把路都反过来从n倒做一次取最大。在枚举i得到max(max[i]-min[i]);
AC代码:
#include <iostream> using namespace std; int num[]; int map[],nxt[]; int las; int head[]; int map2[],nxt2[]; int las2; int head2[]; void adad(int a,int b) { map[las]=b; nxt[las]=head[a]; head[a]=las++; } void adad2(int a,int b) { map2[las2]=b; nxt2[las2]=head2[a]; head2[a]=las2++; } #define Q_MAX 100000 int used[]; int queue[Q_MAX]; int h,r; void enq(int k) { if (used[k]) return; used[k]=; queue[r]=k; r=(r+)%Q_MAX; } int exq() { int t; t=queue[h]; used[t]=; h=(h+)%Q_MAX; return t; } int minn[]; int maxn[]; int main() { int i,j; int n,m; int a,b,c; cin >> n >> m; for (i=;i<n;i++) { head[i]=head2[i]=-; maxn[i]=-; minn[i]=0xFFFFFFF; cin >> num[i]; } for (i=;i<m;i++) { cin >> a >> b >> c; a--,b--; if (c==) { adad(a,b); adad(b,a); adad2(a,b); adad2(b,a); } else { adad(a,b); adad2(b,a); } } minn[]=num[]; enq(); while (h!=r) { i=exq(); for (a=head[i];a!=-;a=nxt[a]) { j=map[a]; if (minn[j]>minn[i]) { minn[j]=minn[i]; enq(j); } if (minn[j]>num[j]) { minn[j]=num[j]; enq(j); } } } maxn[n-]=num[n-]; enq(n-); while (h!=r) { i=exq(); for (a=head2[i];a!=-;a=nxt2[a]) { j=map2[a]; if (maxn[j]<maxn[i]) { maxn[j]=maxn[i]; enq(j); } if (maxn[j]<num[j]) { maxn[j]=num[j]; enq(j); } } } for (i=a=;i<n;i++) if (a<maxn[i]-minn[i]) a=maxn[i]-minn[i]; cout << a << "\n"; return ; }
T4:靶形数独
题目大意:解一个多解数独,从内向外分数不同,求分数最大的解法。
思路:解法肯定还是一样的,dfs。然后比较分数大小输出最大的。
然而这样会超时,codevs上可以过但是最慢的点用了2400多ms,时限4秒。
借鉴了一下某位神牛,用位运算加快运算速度(难写啊啊啊),试了一下还是能过的。
AC代码:
#include<iostream> #include<cmath> using namespace std; int h[]={},hs[]={},zs[]={},xj[][]={},hq[]={}; int ans=-,st[],a[][]; void make() { int i,j,sum=; for (i=;i<;i++) { for (j=i;j<-i;j++) sum+=(a[i][j]+a[-i][j])*(+i); for (j=i+;j<-i;j++) sum+=(a[j][i]+a[j][-i])*(+i); } sum+=a[][]*; if (sum>ans) ans=sum; } void dfs(int k) { if (k==) make(); else { int x,y,j,pos,p,i=st[k]; x=-h[i]; y=x&-x; h[i]|=y; j=(int)log2(y)+; pos=-(hs[i]|zs[j]|xj[(i-)/][(j-)/]); while (pos>) { p=pos&-pos; pos-=p; a[i][j]=(int)log2(p)+; hs[i]|=p; zs[j]|=p; xj[(i-)/][(j-)/]|=p; if (x==y) dfs(k+); else dfs(k); hs[i]-=p; zs[j]-=p; xj[(i-)/][(j-)/]-=p; } h[i]-=y; } } int main() { int i,j,p0; for (i=;i<;i++) for (j=;j<;j++) { cin >> a[i][j]; if (a[i][j]>) { h[i]|=<<(j-); p0=<<(a[i][j]-); if (((hs[i]&p0)!=)||((zs[j]&p0)!=)||((xj[(i-)/][(j-)/]&p0)!=)) { cout << "-1\n"; return ; } hs[i]|=p0; zs[j]|=p0; xj[(i-)/][(j-)/]|=p0; } else hq[i]++; } for (i=;i<;i++) st[i]=i; for (i=;i<;i++) for (j=i+;j<;j++) if (hq[st[i]]>hq[st[j]]) { st[i]^=st[j]; st[j]^=st[i]; st[i]^=st[j]; } i=; while (hq[st[i]]==) i++; dfs(i); cout << ans << "\n"; return ; }
最新文章
- Android xml资源文件中@、@android:type、@*、?、@+含义和区别
- python 基本语法
- ";+"; 是怎样连接字符串的?
- LINUX下WIFI默认连接
- -(UIView *)hitTest:(CGPoint)point withEvent:(UIEvent *)event
- React.js再探(四)
- WebApi Ajax 跨域请求解决方法(CORS实现)(作者:jianxuanbing)
- idea 配置热部署
- Homework 7 INF 552
- 通过ssh StrictHostKeyChecking解决自动化git项目问题
- react组件传值传方法
- jdbc 接口的用法 Statement和PreparedStatement的区别!
- /etc/profile
- 官方文档:Office VBA 参考
- 有序列表ol和定义列表dl,dt,dd
- BOM*创建工艺路线
- SQL 测验
- sqlserver根据条件生成插入语句--单表
- mysql数据库配置主从同步
- 条件查询Criteria