摘要: 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... 閱讀全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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 | 29 | 30 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|
常用鏈接
留言簿
隨筆分類
隨筆檔案
傳送門
搜索
最新評論
閱讀排行榜
評論排行榜
|
|