摘要: http://acm.fzu.edu.cn/problem.php?pid=19182010福州邀请赛 J 题
#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<complex>using namespace s... 阅读全文
摘要: http://acm.fzu.edu.cn/problem.php?pid=1905 浙江理工邀请赛G题的进化版,AC大牛出的题,专门卡矩阵做法的,不用AC大牛的做法至今无人能过,比赛的时候想起来AC大牛的blog中有写过解法的,跑去AC大牛blog一看,已经被删除啦。。。唉,怪自己当初没有好好研究AC... 阅读全文
这学期选了《Windows程序设计》这门课,被Windows应用程序的字符集给弄死了。 每次作业都要在字符的问题上纠结好久。。。终于找到了一个比较猥琐的方法,直接改工程的属性,将字符集定义为“未定义”,那么就是用ASNII编码来写的,TCHAR之类的都被typedef 为char了,汉字的话用两个字节存放,并且两个字节的值<0,在只有英文跟中文的前提下,那么就可以很快判断汉字和英文了。唉,继续纠结吧。。。
不要堕落!!! Come on ! ! coreBug ! !
摘要: http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1990 题目的意思是求出一些点,使得这些点到给定的一些直线的距离相等,只有一个点的时候输出该点,多个点那么输出"Many",没有符合的点那么输出"None",大致的做法是:先用角平分线求出一定量的点(最多4个),然后枚举检查这些点,精度有点搞!!!
#include&... 阅读全文
http://acm.hdu.edu.cn/showproblem.php?pid=3411 浙江理工邀请赛G题,又是一道比赛的时候没有做出来的题目,当时思路被题目给的公式限制住了,一看有除法又要取模,而且数据都很大,觉得没有办法入手,就跳过了。赛后,发现是可以构造矩阵做-_-||| 唉,被题目给的公式限制了思路啊。。。 设 An = (-q)^n Sn = sigma ( Ai ),i = 0, 1,..., n | Sn | = | 1, 1 | * | Sn-1 | | An+1| | 0, -q | | An | Sn = ( 1 - ( -q )^n ) / ( 1 + q ) 则 f( n ) = | S(n-1) |, 注意是绝对值的S(n-1),因为题目中的f( n ) 是一个正数,就是因为这里没弄清楚WA了一次。 以下是我的代码:
// | Sn | = | 1, 1 | * | Sn-1 | // | An+1 | | 0, -q | | An | #include<iostream> using namespace std; typedef __int64 ll; ll p; ll pow_mod( ll a, ll n, ll z1 ) { ll ans = 1, d = a % p; while( n ) { if( n & 1 ) ans = ( ans * d ) % p; d = ( d * d ) % p; n >>= 1; } ans = ( ans + z1 ) % p; ans = ( p - ans ) % p; return ans; }
void matrix_mod( ll a[][2], ll b[][2] ) { ll c[2][2]; int i, j, k; memset( c, 0, sizeof( c ) ); for( k = 0; k < 2; k++ ) for( i = 0; i < 2; i++ ) for( j = 0; j < 2; j++ ) c[k][i] += a[k][j] * b[j][i]; for( i = 0; i < 2; i++ ) for( j = 0; j < 2; j++ ) a[i][j] = c[i][j] % p; }
ll Mod( ll x1, ll y1, ll z1, ll y2, ll z2 ) { int i, j, k; ll q = pow_mod( x1, y1, z1 ); ll a[2][2], I1[2][2], I2[2][2]; a[0][0] = 1, a[0][1] = 1, a[1][0] = 0, a[1][1] = q; I1[0][0] = 1, I1[0][1] = 0, I1[1][0] = 0, I1[1][1] = 1; while( z2 ) { if( z2 & 1 ) matrix_mod( I1, a ); matrix_mod( a, a ); z2 >>= 1; } a[0][0] = 1, a[0][1] = 1, a[1][0] = 0, a[1][1] = q; I2[0][0] = 1, I2[0][1] = 0, I2[1][0] = 0, I2[1][1] = 1; for( i = 0; i < y2; i++ ) { matrix_mod( I2, a ); matrix_mod( a, a ); } memset( a, 0, sizeof( a ) ); for( i = 0; i < 2; i++ ) for( j = 0; j < 2; j++ ) for( k = 0; k < 2; k++ ) a[i][j] += I1[i][k] * I2[k][j]; for( i = 0; i < 2; i++ ) for( j = 0; j < 2; j++ ) a[i][j] %= p; return ( a[0][0] + a[0][1] * q ) % p; }
int main( ) { ll x1, y1, z1, y2, z2; ll ans; while( 1 ) { scanf("%I64d%I64d%I64d",&x1,&y1,&z1); if( x1 == -1 && y1 == -1 && z1 == -1 )break; scanf("%I64d%I64d%I64d",&y2,&z2,&p); ans = Mod( x1, y1, z1, y2, z2 ); if( ( y2 == 0 && z2 % 2 == 1 ) || ( y2 != 0 && z2 % 2 == 0 ) ) ans = p - ans; printf("%I64d\n",ans); } return 0; }
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3408浙江理工邀请赛D题,比赛的时候没有搞出来,赛后终于一次AC了,题目其实还是比较简单的,模拟一下就可以了。
#include<iostream>#include<cmath>#include<complex>#include<algorithm>using&n... 阅读全文
终于赶回来了,先开个头,很晚了,明天再写。
终于有时间可以继续这篇blog了。 这次杭州之行,是coreBug第一次参加现场赛。虽然这不是我第一次参加现场赛,但是我还是感觉紧张,因为之前参加的比赛都打了铁,心理有点阴影,加之A题是一道模板题,却卡了三次。 最早入手的题目是A题,一道MST模板题,zjshark迅速敲好后,提交,返回一个WA,心里不禁一惊。于是ZZZ帮zjshark查错,我继续读题。时间大概过了20分钟,看着旁边的气球一个一升起,我们却依旧是空空的,心里难免有点紧张了。过了一会儿,我发现H题也是一道水题,一个暴力的模拟题,跟zjshark说了一下题意,他迅速AC掉H,提升了一下士气。然后ZZZ继续来改A,又提交了两次还是WA,真是奇怪了,MST看来看去没有错,自己测了几组数据也是对的,想不通了。这时,我跟zjshark把F研究的差不多了,用队列来模拟,由于数据量比较大,加了RMQ来加快查询。等我们刚想准备写F时,ZZZ发现了A中的错误,原来是min的类型用错了,本该用double的,结果使用了int,导致每次找出来的最小值都被截断了,而测试数据中刚好都是整数,所以没有影响,也就导致了3次WA,汗啊。。。低级错误。。。迅速AC掉A题之后,我们也迅速了AC掉了F题。这时时间差不多过去了3个小时,我们还只做出了三道题目。旁边北大队伍的气球已经数不过来了。。。接下来是D题,这是一道比较简单的计算几何,但是由于我的紧张,思路没有打开,在一个判断上没有想清楚,导致代码敲起来没有头绪。zjshark和ZZZ继续研究其他题目,他们发现I题也比较简单,一道模拟题,我让出机器给zjshark敲,结果又卡住了,后来他们推测是精度问题,我帮zjshark调了一会儿,在WA了两次之后AC了,这是已经封版了。由于其他题目不是太烦就是没有想法,大家决定最后的时间差不多只能由我来敲D了。结果还是辜负了队友的期望了,D题WA了好多次,一直到比赛结束都没有过。。。 这次比赛总的来说还是比较满意的,毕竟不打铁了,拿了一个铜牌。这场比赛也暴露出了很多问题,三个人之间的配合,还有掌握的算法的广度,对linux系统的熟悉程度都是有很大问题的,还有就是平时是三台电脑,现在是一台电脑,感觉完全不一样。coreBug还要多加努力啊。 在此顺便膜拜一下Puzzle夺金,Starshine最佳女队,安慰下Bread,三人都是第一次参赛能做出两题很不错啦。
摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=3525半平面交
#include<iostream>#include<deque>#include<algorithm>#include<cmath>#include<complex>#include<cstdio>#include&... 阅读全文
第七届浙江省赛C题 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3749
比赛的时候还是很容易就想到了“线段树+离散化”,说明之前一些线段树的题目做了还是有效果的。但是接下来就是悲剧的时刻,没有想清楚怎么离散化,还有就是更新的函数,构造不出来,知道“线段树+离散化”又有什么用呢?唉,对线段树理解地不够深刻的。。。由于比赛中这道题目的AC率不高,我们队还有一些很多人通过的题没有AC,我就立马放弃了这道题,想最后还有时间的话,再来想想。 跟预想的一样,比赛的时候是没有时间再看这道题了。 比赛结束之后,看到了解题报告,后来又参看了http://boskijr.is-programmer.com/posts/17295.html#more Boski Jr.的代码,然后终于AC了。 学到了一招比较好的离散化的方式,使用半开半必的区间,比如 [ a , b ] 可以用 [ a, b+1 ) 来代替,可以省下不少空间呢。 以下是我的代码:
#include<iostream> #include<algorithm> #include<cmath> using namespace std;
struct node { int s,t; char op[3]; }; struct segment { int l,r; int left,right; // 记录区间两端的高度 int flag; // 记录整段区间被下压的次数 int count; // 记录区间中处于高度0的条数 };
const int maxn = 21000; node a[maxn]; segment tree[maxn<<3]; int lisan[maxn<<1];
void make_tree( int v, int l, int r ) { int mid; tree[v].l = l, tree[v].r = r; tree[v].flag = tree[v].left = tree[v].right = 0; tree[v].count = 1; if( l + 1 != r ) { mid = ( l + r ) >> 1; make_tree( v<<1, l, mid ); make_tree( ( v<<1 ) + 1, mid, r ); } }
void update( int v, int s, int t, int c ) { int mid; if( lisan[tree[v].l] == s && lisan[tree[v].r] == t ) { tree[v].flag += c; tree[v].left += c; tree[v].right += c; if( tree[v].flag ) // 如果区间高度不是0,说明被下压,没有0线段 tree[v].count = 0; else // 叶子节点 if( tree[v].l + 1 == tree[v].r ) tree[v].count = 1; else // 一般节点 tree[v].count = tree[v<<1].count + tree[(v<<1)+1].count - ( tree[v<<1].right == 0 && tree[(v<<1)+1].left == 0 ); return ; } mid = ( tree[v].l + tree[v].r ) >> 1; if( lisan[mid] >= t ) update( v<<1, s, t, c ); else if( lisan[mid] <= s ) update( (v<<1)+1, s, t, c ); else { update( v<<1, s, lisan[mid], c ); update( (v<<1)+1, lisan[mid], t, c ); } tree[v].left = tree[v<<1].left + tree[v].flag; tree[v].right = tree[(v<<1)+1].right + tree[v].flag;
if( tree[v].flag ) tree[v].count = 0; else tree[v].count = tree[v<<1].count + tree[(v<<1)+1].count - ( tree[v<<1].right == 0 && tree[(v<<1)+1].left == 0 ); }
void init( int n, int m ) { int i,len=0; lisan[len++] = 0; lisan[len++] = n; for( i = 0; i < m; i++ ) { scanf("%s%d%d",a[i].op,&a[i].s,&a[i].t); a[i].t++; lisan[len++] = a[i].s; lisan[len++] = a[i].t; } sort( lisan, lisan + len ); len = unique( lisan, lisan + len ) - lisan; make_tree( 1, 0, len-1 ); }
int main( ) { int i,t,n,m,k = 1; scanf("%d",&t); while( t-- ) { scanf("%d%d",&n,&m); init( n, m ); printf("Case #%d:\n",k++); for( i = 0; i < m; i++ ) { update( 1, a[i].s, a[i].t, ( a[i].op[0] == 'p' ? 1 : -1 ) ); printf("%d\n",tree[1].count); } } return 0; }
摘要: 这几天做了一些Fibnacci的题目,基本思想是构造矩阵,对于求余的时候,模上的数比较小的时候可以用循环节来做。1、http://acm.hdu.edu.cn/showproblem.php?pid=1021求fib(n) mod 3是否为0,构造矩阵,代码略。2、http://acm.hdu.edu.cn/showproblem.php?pid=1568求fib的前4位数,当n比较小的时候,直接... 阅读全文
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3372太晚了,先贴代码。。。
1#include<iostream> 2#include<cmath> 3#include<complex> 4#include<algorit... 阅读全文
http://acm.pku.edu.cn/JudgeOnline/problem?id=3026 这道题的输入数据及其猥琐,有很多无用的空格。。。 其他还是没什么的,只要BFS处理下两点间的距离,然后MST一下。。。
// 3026 Borg Maze // Time Limit: 1000MS Memory Limit: 65536K // Total Submissions: 2827 Accepted: 888
#include<iostream> #include<queue> #define MAXN 105 #define N 55 #define INF 10000000 using namespace std; struct node { int x,y; int step; }; int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; char maze[N][N]; bool vis[N][N]; int g[MAXN][MAXN],v[N][N]; node d[MAXN]; int n,m,cnt; void BFS( node a ) { int i,x,y,nx,ny,step; node p; queue<node> que; memset( vis, false, sizeof(vis) ); que.push( a ); vis[a.x][a.y]=true; while( !que.empty( ) ) { p=que.front( ); que.pop( ); x=p.x,y=p.y,step=p.step+1; for( i=0; i<4; i++ ) { nx=x+dir[i][0],ny=y+dir[i][1]; if( nx<m && nx>=0 && ny<n && ny>=0 && !vis[nx][ny]) { if( maze[nx][ny]=='S' || maze[nx][ny]=='A' ) { g[v[a.x][a.y]][v[nx][ny]]=g[v[nx][ny]][v[a.x][a.y]]=step; p.x=nx,p.y=ny,p.step=step; que.push( p ); vis[nx][ny]=true; } if( maze[nx][ny]==' ' ) { p.x=nx,p.y=ny,p.step=step; que.push( p ); vis[nx][ny]=true; } } } } }
void create_graph( ) { int i,j; for( i=0; i<m; i++ ) gets( maze[i] ); cnt=0; for( i=0; i<m; i++ ) for( j=0; j<n; j++ ) if( maze[i][j]=='A' || maze[i][j]=='S' ) d[cnt].x=i,d[cnt].y=j,d[cnt].step=0,v[i][j]=cnt++; for( i=0; i<cnt; i++ ) for( g[i][i]=0, j=i+1; j<cnt; j++ ) g[i][j]=g[j][i]=INF; for( i=0; i<cnt; i++ ) BFS( d[i] ); }
int prim( ) { int i,j,k,min,ans; int dis[MAXN]; for( i=0; i<cnt; i++ ) dis[i]=g[0][i]; ans=0; for( i=1; i<cnt; i++ ) { min=INF,k=-1; for( j=0; j<cnt; j++ ) if( dis[j] && dis[j]<min ) min=dis[j],k=j; ans+=min; dis[k]=0; for( j=0; j<cnt; j++ ) if( dis[j] && g[k][j]<dis[j] ) dis[j]=g[k][j]; } return ans; }
int main( ) { int ans,t; char c[100]; scanf("%d",&t); while( t-- ) { scanf("%d%d",&n,&m); gets( c ); create_graph( ); ans=prim( ); printf("%d\n",ans); } return 0; }
摘要: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3299zoj 月赛的时候没有解出来,当时以为是二维线段树,由于二维的一道都没写过,所以这题被我放弃了,后来看了别人的解题报告,原来是一维的。。。先按高度给line从小到大排序,然后按顺序插入木板,后面可以覆盖前面的,然后再在线段树上插入砖块,用一个num域来表示这... 阅读全文
摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
#include<iostream>#include<algorithm>#define MAXN 10005using namespace std;struct segment{ int L,R;&nb... 阅读全文
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论
阅读排行榜
评论排行榜
|
|