poao899 28K 4840MS G++ 0.36K 2010-03-31 02:50:18 .
頗有趣的DP。
雷:
狀態存法 dp[n大小][該序列尾數] 但是這樣是10^8記憶體會爆炸
所以滾動。
另外是%100000007所以小心溢位。
轉移方式: dp[i-1][k] + 結尾k or k+1 以及 開頭+1~k
//*******************************
#include<stdio.h>
#define MODE 100000007
int dp[10010], n, t;
long long tmp;
int main(){
scanf("%d", &n);
dp[1]= 1;
for(int i=2; i<=n; i++){
for(int j=i; j>0; j--){
dp[j+1]+= dp[j];
dp[j+1]%= MODE;
tmp= (long long)dp[j]*j;
dp[j]= (int)(tmp%MODE);
}
}
for(int i=1; i<=n; i++){
t+= dp[i];
t%= MODE;
}
printf("%d\n", t);
}
2010年3月30日 星期二
POI - PA 2006 Crayfish (精神+翻譯)
沒co出來的有趣圖論 .
Round 4的題目好有趣但是好難orz
//*************************************
翻譯
給你一張有向圖，n<=10^4個頂點，m<=10^5條邊
有些邊是特殊的邊。
現在假設我拿i為起點，一開始只能逆的走(i.e. a->b的邊只能從b走到a)
然後每經過一次特殊邊就得換方向(正走-> 逆走 反之亦然)
問你對於每個點的val值，val值定義為 從該點出發並要回到該點最多能經過多少其他的點
Input:
//***********************************
雷:
把除了特殊的邊以外的正向圖及反向圖皆分別建出來，
每一條特殊的邊ex: a -> b
那麼就會從正向圖的a和反向圖的b做雙向邊
建完圖後SCC, 判重(同時走過一個點的正向跟反向)
//************************************
Round 4的題目好有趣但是好難orz
//*************************************
翻譯
給你一張有向圖，n<=10^4個頂點，m<=10^5條邊
有些邊是特殊的邊。
現在假設我拿i為起點，一開始只能逆的走(i.e. a->b的邊只能從b走到a)
然後每經過一次特殊邊就得換方向(正走-> 逆走 反之亦然)
問你對於每個點的val值，val值定義為 從該點出發並要回到該點最多能經過多少其他的點
Input:
5 5
2 1 1
2 3 0
3 4 0
4 2 0
5 3 1
Output:
3
3
3
3
0
//***********************************
雷:
把除了特殊的邊以外的正向圖及反向圖皆分別建出來，
每一條特殊的邊ex: a -> b
那麼就會從正向圖的a和反向圖的b做雙向邊
建完圖後SCC, 判重(同時走過一個點的正向跟反向)
//************************************
POI - PA 2007 Encyclopedia [B]
30-03-10 11:10 Encyclopedia [B] OK 10 .
頗白癡的題目我說= =
說實話有點不值得Round 3的水準
就是給你一個由n個1 n個0組成的序列，每次交換相鄰兩個
問你把它轉成101010.... 或010101.... 最少要幾步
//***********************************
頗白癡的題目我說= =
說實話有點不值得Round 3的水準
就是給你一個由n個1 n個0組成的序列，每次交換相鄰兩個
問你把它轉成101010.... 或010101.... 最少要幾步
//***********************************
#include<stdio.h>
int in, n, pos, pos2;
long long ans, ans2;
long long abs(int a, int b){
if(a> b)return (long long)a-b;
return (long long)b-a;
}
int main(){
scanf("%d", &n);
pos= 1; pos2= 1;
for(int i=0; i<2*n; i++){
scanf("%d", &in);
if(in== 0){
ans+= abs(pos, i);
pos+= 2;
}else{
ans2+= abs(pos2, i);
pos2+= 2;
}
}
printf("%lld\n", ans<ans2? ans: ans2);
}
2010年3月29日 星期一
POI - PA 2008 Diagonals [B]
| User: | Chen Kuei-yi (poao899) |
| Date: | 2010-03-30 03:44:39 |
| Points | 10 |
| Comment: | Algorithmic Engagements 2008, Round 3 |
| Task: | prz/Diagonals [B] |
| Date: | 2010-03-30 05:04:08 |
| Points: | 10/10 |
| Files: | solution |
|
不對啊AC沒道理啊 O(m lg m)sort +O(n)stack
m<=10^7, n<=10^6
怎麼看都不會AC的複雜度
還有拿掉gn跑得比較快ˊˋ
勝利得一點都不開心orz
對了，測資大概灌水兩倍
//*****************************************
#include<algorithm>
#define M 5000010
int n,m,q[M],r;
struct dia{
int i, j, o;
void get(int oo){
scanf("%d%d", &i, &j); o=oo;
if(i>j){i^=j^=i^=j;}
}
bool operator< (const dia &b)const{
return i<b.i || i==b.i&&j>b.j;
}
}d[M];
struct dia2{
int i, j, o;
void set(int ii, int jj, int oo){
i=ii; j=jj; o=oo;
}
bool operator< (const dia2 &b)const{
return j<b.j || j==b.j&&i>b.i;
}
}d2[M];
int main(){
scanf("%d%d", &n, &m);
if(m>M)m=M;
for(int i=0; i<m; i++){
d[i].get(i+1);
d2[i].set(d[i].i, d[i].j, i+1);
}
std::sort(d, d+m);
std::sort(d2, d2+m);
int di=0, di2=0;
for(int i=1; i<=n; i++){
for(; di2<m; di2++){
if(d2[di2].j==i){
if(q[r-1]== d2[di2].o){
r--;
}else{
printf("%d %d\n",q[r-1], d2[di2].o);
return 0;
}
}else break;
}
for(; di<m; di++){
if(d[di].i==i){
q[r]= d[di].o;
r++;
}else break;
}
}
puts("NIE");
}
TIOJ 1132 Dark Horse Escape [Greedy]
poao899 1776K 265MS G++ 0.66K 2010-03-29 19:08:07 .
反正擋他的位置一定不會比拐馬腳差...
//**********************************
反正擋他的位置一定不會比拐馬腳差...
//**********************************
#include<stdio.h>
#include<algorithm>
bool map[1011][1011];
struct horse{
int x, y;
bool operator<(const horse &b)const{
return x<b.x || x==b.x&&y<b.y;
}
void get(){
scanf("%d%d", &x, &y);
map[x][y]= 1;
}
}h[100010];
int n, cnt;
int main(){
while(~scanf("%d", &n)){
cnt= 0;
for(int i=0; i<1011; i++)
for(int j=0; j<1011; j++)
map[i][j]= 0;
for(int i=0; i<n; i++)
h[i].get();
std::sort(h, h+n);
for(int i=0; i<n; i++){
int x= h[i].x, y= h[i].y;
if(!map[x+1][y+2]&& !map[x][y+1])
{map[x+1][y+2]= 1; cnt++;}
if(!map[x+2][y+1]&& !map[x+1][y])
{map[x+2][y+1]= 1; cnt++;}
}
printf("%d\n", cnt);
}
}
2010年3月28日 星期日
TIOJ 1528 一字千金 [Tree]
poao899 4420K 6666MS G++ 2.34K 2010-03-29 13:51:35 .
本篇全部都是雷(?
阿思：就把他想成一棵樹多了8條邊，然後去枚舉就好了
說實話也不好枚舉orz
一開始很直覺的2^8= 256的枚舉
可以想一下以下這組測資
3 3
10 100 10
1 2
2 3
1 3
答案應該是100
但是3^8= 6561太大了會TLE
而且還有一組測資
3 4
10 10 10
1 2
2 3
3 1
1 2
答案絕對是10
然後下面那組真的是我自己的問題了orz
8 9
6 3 5 2 5 3 1 4
1 2
2 4
4 5
6 4
4 8
5 7
3 5
2 6
7 8
答案是18
所以就變成2^8 *(O(e)檢查 + O(v)DP)
//*******************************
#include<stdio.h>
long long dp[50100][2], max;
int deter[50100], speCnt, n, m, val[50100], a, b, ra, rb;
int root[50100], fa[50100];
int find(int a){return root[a]==a? a: root[a]=find(root[a]);}
//0= no 1= 一定要 2= 一定不能
struct edge{
int i, j;
edge *next;
}e[100100], spe[10], *p, *v[50100];
void dfs(int n){
bool can= 1;
dp[n][0]= dp[n][1]= 0;
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
fa[ptr->j]= n;
dfs(ptr->j);
if(deter[ptr->j]== 1)
can= 0;
}
if(deter[n]!= 2&& can){
dp[n][1]= val[n];
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
dp[n][1]+= dp[ptr->j][0];
}
}if(deter[n]!=1){
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
if(deter[ptr->j]==2)
dp[n][0]+= dp[ptr->j][0];
else if(deter[ptr->j]==1)
dp[n][0]+= dp[ptr->j][1];
else dp[n][0]+= dp[ptr->j][0]>dp[ptr->j][1]? dp[ptr->j][0]: dp[ptr->j][1];
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
root[i]= i;
scanf("%d", val+i);
}
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b);
ra= find(a);
rb= find(b);
if(ra==rb){
spe[speCnt].i=a; spe[speCnt].j=b;
speCnt++;
}else{
e[i].i=a; e[i].j=b;
p=v[a]; v[a]=&e[i]; e[i].next=p;
e[i+m].i=b; e[i+m].j=a;
p=v[b]; v[b]=&e[i+m]; e[i+m].next=p;
root[rb]= ra;
}
}
int ii= 1<<speCnt;
for(int i=0; i<ii; i++){
//init
bool can= 1;
for(int j=1; j<=n; j++)
fa[j]=j;
for(int j=0; can&& j<speCnt; j++){
if(i& (1<<j)){
deter[spe[j].i]= 2;
deter[spe[j].j]= 0;
}else{
deter[spe[j].i]= 1;
deter[spe[j].j]= 2;
}
}
for(int i=0; can&& i<m; i++)
if(deter[e[i].i]== 1&& deter[e[i].j]== 1)
can=0;
for(int i=0; can&& i<speCnt; i++)
if(deter[spe[i].i]== 1&& deter[spe[i].j]== 1)
can=0;
if(!can)continue;
dfs(root[1]);
for(int j=0; j<2; j++)
if(dp[root[1]][j]> max)
max=dp[root[1]][j];
}
printf("%I64d\n",max);
}
本篇全部都是雷(?
阿思：就把他想成一棵樹多了8條邊，然後去枚舉就好了
說實話也不好枚舉orz
一開始很直覺的2^8= 256的枚舉
可以想一下以下這組測資
3 3
10 100 10
1 2
2 3
1 3
答案應該是100
但是3^8= 6561太大了會TLE
而且還有一組測資
3 4
10 10 10
1 2
2 3
3 1
1 2
答案絕對是10
然後下面那組真的是我自己的問題了orz
8 9
6 3 5 2 5 3 1 4
1 2
2 4
4 5
6 4
4 8
5 7
3 5
2 6
7 8
答案是18
所以就變成2^8 *(O(e)檢查 + O(v)DP)
//*******************************
#include<stdio.h>
long long dp[50100][2], max;
int deter[50100], speCnt, n, m, val[50100], a, b, ra, rb;
int root[50100], fa[50100];
int find(int a){return root[a]==a? a: root[a]=find(root[a]);}
//0= no 1= 一定要 2= 一定不能
struct edge{
int i, j;
edge *next;
}e[100100], spe[10], *p, *v[50100];
void dfs(int n){
bool can= 1;
dp[n][0]= dp[n][1]= 0;
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
fa[ptr->j]= n;
dfs(ptr->j);
if(deter[ptr->j]== 1)
can= 0;
}
if(deter[n]!= 2&& can){
dp[n][1]= val[n];
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
dp[n][1]+= dp[ptr->j][0];
}
}if(deter[n]!=1){
for(edge *ptr=v[n]; ptr; ptr=ptr->next){
if(fa[n]== ptr->j)continue;
if(deter[ptr->j]==2)
dp[n][0]+= dp[ptr->j][0];
else if(deter[ptr->j]==1)
dp[n][0]+= dp[ptr->j][1];
else dp[n][0]+= dp[ptr->j][0]>dp[ptr->j][1]? dp[ptr->j][0]: dp[ptr->j][1];
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
root[i]= i;
scanf("%d", val+i);
}
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b);
ra= find(a);
rb= find(b);
if(ra==rb){
spe[speCnt].i=a; spe[speCnt].j=b;
speCnt++;
}else{
e[i].i=a; e[i].j=b;
p=v[a]; v[a]=&e[i]; e[i].next=p;
e[i+m].i=b; e[i+m].j=a;
p=v[b]; v[b]=&e[i+m]; e[i+m].next=p;
root[rb]= ra;
}
}
int ii= 1<<speCnt;
for(int i=0; i<ii; i++){
//init
bool can= 1;
for(int j=1; j<=n; j++)
fa[j]=j;
for(int j=0; can&& j<speCnt; j++){
if(i& (1<<j)){
deter[spe[j].i]= 2;
deter[spe[j].j]= 0;
}else{
deter[spe[j].i]= 1;
deter[spe[j].j]= 2;
}
}
for(int i=0; can&& i<m; i++)
if(deter[e[i].i]== 1&& deter[e[i].j]== 1)
can=0;
for(int i=0; can&& i<speCnt; i++)
if(deter[spe[i].i]== 1&& deter[spe[i].j]== 1)
can=0;
if(!can)continue;
dfs(root[1]);
for(int j=0; j<2; j++)
if(dp[root[1]][j]> max)
max=dp[root[1]][j];
}
printf("%I64d\n",max);
}
TIOJ 1325 倍因道 - EXTREME
poao899 1948K 326MS G++ 0.89K 2010-03-29 00:10:54 .
我說code風格好醜= =
然後用1241來Debug...不行 思路不夠清楚
O(n ln n)+ T*O(1)
//**************************
#include<stdio.h>
#include<algorithm>
#define MAX 100000
struct stuff{
int ori, cmp;
bool operator<(const stuff &b)const{
return cmp<b.cmp;
}
}s[100010];
int sieve[100010], dp[100010], get[100010], t, n;
int main(){
for(int i=1; i<=MAX; i++)
for(int j=i+i; j<=MAX; j+=i)
sieve[j]++;
for(int i=1; i<=MAX; i++){
s[i-1].ori= i;
s[i-1].cmp= (sieve[i]+1)* i;
}
std::sort(s, s+MAX);
for(int i=1,j=0; i<=MAX; i++){
dp[i]= dp[i-1];
while(j<MAX&& s[j].cmp<=i){
dp[i]-= sieve[s[j].ori];
for(int z=s[j].ori*2; z<=MAX; z+=s[j].ori){
if(z<i)dp[i]++;
get[z]++;
}
j++;
}
dp[i]+= get[i];
}
scanf("%d", &t);
while(t--){
scanf("%d", &n);
printf("%d\n", dp[n]);
}
}
我說code風格好醜= =
然後用1241來Debug...不行 思路不夠清楚
O(n ln n)+ T*O(1)
//**************************
#include<stdio.h>
#include<algorithm>
#define MAX 100000
struct stuff{
int ori, cmp;
bool operator<(const stuff &b)const{
return cmp<b.cmp;
}
}s[100010];
int sieve[100010], dp[100010], get[100010], t, n;
int main(){
for(int i=1; i<=MAX; i++)
for(int j=i+i; j<=MAX; j+=i)
sieve[j]++;
for(int i=1; i<=MAX; i++){
s[i-1].ori= i;
s[i-1].cmp= (sieve[i]+1)* i;
}
std::sort(s, s+MAX);
for(int i=1,j=0; i<=MAX; i++){
dp[i]= dp[i-1];
while(j<MAX&& s[j].cmp<=i){
dp[i]-= sieve[s[j].ori];
for(int z=s[j].ori*2; z<=MAX; z+=s[j].ori){
if(z<i)dp[i]++;
get[z]++;
}
j++;
}
dp[i]+= get[i];
}
scanf("%d", &t);
while(t--){
scanf("%d", &n);
printf("%d\n", dp[n]);
}
}
TIOJ 1130 Dark Kingdom II [Greedy]
poao899 228K 546MS G++ 0.81K 2010-03-28 15:22:42 .
奇怪最近寫一大堆Greedy
是說我無法證明這是正確的耶zzz
只是覺得超合理 寫起來超毛的
而且看著大家的code length 好像只有我有co Heap 耶Q
//**************************
#include<algorithm>
int n, m, st[30000], ed[30000], c1, c2, top;
int main(){
while(~scanf("%d%d",&n,&m)){
c1=c2=0; top=m;
for(int i=0; i<m; i++){
scanf("%d%d", st+i, ed+i);
c1+= (st[i]>ed[i]? ed[i]+n-st[i]: ed[i]-st[i]);
}
std::sort(st, st+m);
for(int i=0; i<m; i++){
if(ed[i]< st[0])
ed[i]+= n;
ed[i]= -ed[i];
}
std::make_heap(ed, ed+top);
for(int i=0; i<m; i++){
while(-ed[0]< st[i]){
std::pop_heap(ed, ed+top--);
ed[top]-= n;
std::push_heap(ed, ed+top++);
}
c2+= -ed[0]-st[i];
std::pop_heap(ed, ed+top--);
}
printf("%d\n", c1-c2);
}
}
奇怪最近寫一大堆Greedy
是說我無法證明這是正確的耶zzz
只是覺得超合理 寫起來超毛的
而且看著大家的code length 好像只有我有co Heap 耶Q
//**************************
#include<algorithm>
int n, m, st[30000], ed[30000], c1, c2, top;
int main(){
while(~scanf("%d%d",&n,&m)){
c1=c2=0; top=m;
for(int i=0; i<m; i++){
scanf("%d%d", st+i, ed+i);
c1+= (st[i]>ed[i]? ed[i]+n-st[i]: ed[i]-st[i]);
}
std::sort(st, st+m);
for(int i=0; i<m; i++){
if(ed[i]< st[0])
ed[i]+= n;
ed[i]= -ed[i];
}
std::make_heap(ed, ed+top);
for(int i=0; i<m; i++){
while(-ed[0]< st[i]){
std::pop_heap(ed, ed+top--);
ed[top]-= n;
std::push_heap(ed, ed+top++);
}
c2+= -ed[0]-st[i];
std::pop_heap(ed, ed+top--);
}
printf("%d\n", c1-c2);
}
}
2010年3月27日 星期六
TIOJ 1133 Dark Teleport Field [Brute Force]
poao899 108K 15MS G++ 2.44K 2010-03-28 14:23:25 .
Debug超超超久orz
原來是兩個矩形的距離算錯
這題只是很暴力不難才對啊orzzzzzzzzzzzzzz
//*************************
#include<stdio.h>
#define QLEN 2000
#define MAXV 160
#define MAXK 10
int d[MAXV][MAXV],dist[MAXV][MAXK];
struct rec{
int x1,y1,x2,y2;
void get(){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
}
int dist(int x,int y){
int d=0;
if(x<x1||x>x2)x<x1? d+=x1-x: d+=x-x2;
if(y<y1||y>y2)y<y1? d+=y1-y: d+=y-y2;
return d;
}
}r[200];
//0 st 1~m rec m+1 ed
int q[QLEN][2],front,rear,n,m,t,k,sx,sy,ex,ey;
bool inq[MAXV][MAXK];
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1; i<=m; i++)
r[i].get();
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++){
d[i][j]= 2147483647;
if(d[i][j]> r[i].dist(r[j].x1, r[j].y1))
d[i][j]= r[i].dist(r[j].x1, r[j].y1);
if(d[i][j]> r[i].dist(r[j].x2, r[j].y1))
d[i][j]= r[i].dist(r[j].x2, r[j].y1);
if(d[i][j]> r[i].dist(r[j].x2, r[j].y2))
d[i][j]= r[i].dist(r[j].x2, r[j].y2);
if(d[i][j]> r[i].dist(r[j].x1, r[j].y2))
d[i][j]= r[i].dist(r[j].x1, r[j].y2);
if(d[i][j]> r[j].dist(r[i].x1, r[i].y1))
d[i][j]= r[j].dist(r[i].x1, r[i].y1);
if(d[i][j]> r[j].dist(r[i].x2, r[i].y1))
d[i][j]= r[j].dist(r[i].x2, r[i].y1);
if(d[i][j]> r[j].dist(r[i].x2, r[i].y2))
d[i][j]= r[j].dist(r[i].x2, r[i].y2);
if(d[i][j]> r[j].dist(r[i].x1, r[i].y2))
d[i][j]= r[j].dist(r[i].x1, r[i].y2);
}
scanf("%d",&t);
while(t-->0){
scanf("%d%d%d%d%d",&k,&sx,&sy,&ex,&ey);
//init
front=0; rear=1;
for(int i=0;i<MAXV;i++){
for(int j=0;j<MAXK;j++){
inq[i][j]=0;
dist[i][j]=1000000000;
}
}
for(int i=1;i<=m;i++){
d[i][0]=d[0][i]=r[i].dist(sx,sy);
d[i][m+1]=d[m+1][i]=r[i].dist(ex,ey);
}
d[0][m+1]= d[m+1][0]= (sx>ex? sx-ex: ex-sx)+ (sy>ey? sy-ey: ey-sy);
q[front][0]= q[front][1]= dist[0][0]= 0; inq[0][0]= 1;
while(front!=rear){
int now=q[front][0], dep=q[front][1];
if(dep<=k){
for(int i=1; i<=m; i++){
if(dist[i][dep+1]> dist[now][dep]+d[now][i]){
dist[i][dep+1]= dist[now][dep]+d[now][i];
if(!inq[i][dep+1]){
q[rear][0]=i;
q[rear][1]=dep+1;
inq[i][dep+1]=1;
rear=++rear%QLEN;
}
}
}
if(dist[m+1][dep]> dist[now][dep]+d[now][m+1])
dist[m+1][dep]= dist[now][dep]+d[now][m+1];
inq[now][dep]=0;
}
front=++front%QLEN;
}
int min=2147483647;
for(int i=0;i<=k;i++)
if(min> dist[m+1][i])
min= dist[m+1][i];
printf("%d\n",min);
}
}
}
Debug超超超久orz
原來是兩個矩形的距離算錯
這題只是很暴力不難才對啊orzzzzzzzzzzzzzz
//*************************
#include<stdio.h>
#define QLEN 2000
#define MAXV 160
#define MAXK 10
int d[MAXV][MAXV],dist[MAXV][MAXK];
struct rec{
int x1,y1,x2,y2;
void get(){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
}
int dist(int x,int y){
int d=0;
if(x<x1||x>x2)x<x1? d+=x1-x: d+=x-x2;
if(y<y1||y>y2)y<y1? d+=y1-y: d+=y-y2;
return d;
}
}r[200];
//0 st 1~m rec m+1 ed
int q[QLEN][2],front,rear,n,m,t,k,sx,sy,ex,ey;
bool inq[MAXV][MAXK];
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1; i<=m; i++)
r[i].get();
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++){
d[i][j]= 2147483647;
if(d[i][j]> r[i].dist(r[j].x1, r[j].y1))
d[i][j]= r[i].dist(r[j].x1, r[j].y1);
if(d[i][j]> r[i].dist(r[j].x2, r[j].y1))
d[i][j]= r[i].dist(r[j].x2, r[j].y1);
if(d[i][j]> r[i].dist(r[j].x2, r[j].y2))
d[i][j]= r[i].dist(r[j].x2, r[j].y2);
if(d[i][j]> r[i].dist(r[j].x1, r[j].y2))
d[i][j]= r[i].dist(r[j].x1, r[j].y2);
if(d[i][j]> r[j].dist(r[i].x1, r[i].y1))
d[i][j]= r[j].dist(r[i].x1, r[i].y1);
if(d[i][j]> r[j].dist(r[i].x2, r[i].y1))
d[i][j]= r[j].dist(r[i].x2, r[i].y1);
if(d[i][j]> r[j].dist(r[i].x2, r[i].y2))
d[i][j]= r[j].dist(r[i].x2, r[i].y2);
if(d[i][j]> r[j].dist(r[i].x1, r[i].y2))
d[i][j]= r[j].dist(r[i].x1, r[i].y2);
}
scanf("%d",&t);
while(t-->0){
scanf("%d%d%d%d%d",&k,&sx,&sy,&ex,&ey);
//init
front=0; rear=1;
for(int i=0;i<MAXV;i++){
for(int j=0;j<MAXK;j++){
inq[i][j]=0;
dist[i][j]=1000000000;
}
}
for(int i=1;i<=m;i++){
d[i][0]=d[0][i]=r[i].dist(sx,sy);
d[i][m+1]=d[m+1][i]=r[i].dist(ex,ey);
}
d[0][m+1]= d[m+1][0]= (sx>ex? sx-ex: ex-sx)+ (sy>ey? sy-ey: ey-sy);
q[front][0]= q[front][1]= dist[0][0]= 0; inq[0][0]= 1;
while(front!=rear){
int now=q[front][0], dep=q[front][1];
if(dep<=k){
for(int i=1; i<=m; i++){
if(dist[i][dep+1]> dist[now][dep]+d[now][i]){
dist[i][dep+1]= dist[now][dep]+d[now][i];
if(!inq[i][dep+1]){
q[rear][0]=i;
q[rear][1]=dep+1;
inq[i][dep+1]=1;
rear=++rear%QLEN;
}
}
}
if(dist[m+1][dep]> dist[now][dep]+d[now][m+1])
dist[m+1][dep]= dist[now][dep]+d[now][m+1];
inq[now][dep]=0;
}
front=++front%QLEN;
}
int min=2147483647;
for(int i=0;i<=k;i++)
if(min> dist[m+1][i])
min= dist[m+1][i];
printf("%d\n",min);
}
}
}
TIOJ 1440 誰買早餐 [Greedy]
poao899 23496K 7525MS G++ 0.56K 2010-03-28 12:53:38 .
空虛題竟然沒有一次AC= =
第一次沒判斷Impossible
第二次沒處理每項早餐只有一個...
營養越高價錢越高
沒這個條件就不知道怎麼做了XD
//**********************************
空虛題竟然沒有一次AC= =
第一次沒判斷Impossible
第二次沒處理每項早餐只有一個...
營養越高價錢越高
沒這個條件就不知道怎麼做了XD
//**********************************
#include<stdio.h>
#include<algorithm>
long long p[1000010],cost;
int n, m;
struct bf{
long long b,c;
void get(){
scanf("%I64d%I64d",&b,&c);
}
bool operator<(const bf &z)const{
return b< z.b;
}
}b[1000010];
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%I64d", p+i);
std::sort(p, p+n);
scanf("%d", &m);
for(int i=0; i<m; i++)
b[i].get();
std::sort(b, b+m);
for(int i=0,j=0; i<n ;i++){
for(; b[j].b<p[i]&&j<m; j++);
if(j==m){puts("Impossible."); return 0;}
cost+= b[j++].c;
}
printf("%I64d\n", cost);
}
TIOJ 1406 魚 FISH [Greedy]
poao899 1556K 545MS G++ 0.68K 2010-03-28 12:31:29 .
奇怪為什麼之前想這麼久
明明沒有很難ˇ 頗可愛的題目>//<
//*****************************
奇怪為什麼之前想這麼久
明明沒有很難ˇ 頗可愛的題目>//<
//*****************************
#include<stdio.h>
long long p[100010], f[100010], mid, l, r;
int n;
long long getl(){
long long g=0;int c=getchar();
while(c==10||c==32||c==9)c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
bool test(){
long long rest=0;
f[0]=mid;
for(int i=1; i<=n; i++){
if(rest)rest-= p[i]-p[i-1];
rest+= f[i]-mid;
}
return rest>=0;
}
int main(){
while(~scanf("%d", &n)){
l=9223372036854775807LL; r=-9223372036854775807LL;
for(int i=1; i<=n; i++){
p[i]=getl(); f[i]=getl();
if(f[i]>r)r=f[i];
if(f[i]<l)l=f[i];
}
while(l!=r){
mid=(l+r+1)/2;
if(test())l=mid;
else r=mid-1;
}
printf("%I64d\n",l);
}
}
TIOJ 1410 Comiket [sort]
poao899 15652K 890MS G++ 0.63K 2010-03-27 20:58:10 .
不想說什麼了orz
只是在寫水題而已...
//************************
不想說什麼了orz
只是在寫水題而已...
//************************
#include<stdio.h>
#include<algorithm>
int n,nowp,maxp,t;
int getint(){
int g=0,c=getchar();
while(c==10||c==32||c==9)c=getchar();
if(c==EOF)return -1;
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
struct peo{
int t,in;
bool operator<(const peo &b)const{
return t<b.t || t==b.t&&in>b.in;
}
}p[2000010];
int main(){
while(~(n=getint())){
nowp=maxp=t=0;
for(int i=0;i<n;i++){
p[t].t=getint();
p[t++].in=1;
p[t].t=getint();
p[t++].in=-1;
}
std::sort(p,p+t);
for(int i=0;i<t;i++){
nowp+=p[i].in;
if(nowp>maxp)maxp=nowp;
}
printf("%d\n",maxp);
}
}
TIOJ 1311 好多星星ver 1.5
nolonger -8K 30MS G++ 0.29K 2010-03-27 19:09:32 .
好糟糕的題目orz
難怪一堆人吃OLE
一次AC的好像只有球主 akira 姜姜跟小乃...
所有數字<=2^31-1
所以用for(int i=x1 ; i<x2 ; i++)在x1=x2=2^31-1就爆炸了...
//****************************
#include<algorithm>
int z,x1,x2,y1,y2,t;
int main(){
while(~scanf("%d",&z)&&z){
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
for(int i=y1; i>0&&i<=y2; i++){
t=std::__gcd(z,i);
for(int j=x1; j>0&&j<=x2; j++)
putchar(std::__gcd(t,j)>1? '.': '*');
puts("");
}puts("--");
}
}
好糟糕的題目orz
難怪一堆人吃OLE
一次AC的好像只有球主 akira 姜姜跟小乃...
所有數字<=2^31-1
所以用for(int i=x1 ; i<x2 ; i++)在x1=x2=2^31-1就爆炸了...
//****************************
#include<algorithm>
int z,x1,x2,y1,y2,t;
int main(){
while(~scanf("%d",&z)&&z){
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
for(int i=y1; i>0&&i<=y2; i++){
t=std::__gcd(z,i);
for(int j=x1; j>0&&j<=x2; j++)
putchar(std::__gcd(t,j)>1? '.': '*');
puts("");
}puts("--");
}
}
TIOJ 1550 鏡框設置回來了!
poao899 72K 2246MS G++ 0.63K 2010-03-27 18:24:24 .
第一個複雜度很好想但是一定會TLE= =
O(nm lg m) -> O(nm)
//***************************
先counting一下，然後檢查每個(上次有出現的數字+1)這次有沒有出現
//***************************
第一個複雜度很好想但是一定會TLE= =
O(nm lg m) -> O(nm)
//***************************
先counting一下，然後檢查每個(上次有出現的數字+1)這次有沒有出現
//***************************
#include <stdio.h>
int dp[1600],n,m,t,max,count[16000];
int l1[1600],l2[1600],top,otop,cnt;
int main(){
int *old=l1,*list=l2,*tmp;
scanf("%d%d\n",&n,&m);
for(int i=0; i
top=cnt=0;
for(int j=0; j
count[old[j]]=0;
for(int j=0; j
getchar()=='1'? dp[j]++: dp[j]=0;
count[dp[j]]++;
}
getchar();
if(count[1])list[top++]=1;
for(int j=0; j
if(count[ old[j]+1 ])
list[top++]= old[j]+1;
for(int j=top-1;j>=0;j--){
cnt+=count[ list[j] ];
t=cnt*list[j];
if(t>max)max=t;
}
tmp=old; old=list; list=tmp; otop=top;
}
printf("%d\n",max);
}
TIOJ 1226 H遊戲 [Graph]
poao899 3772K 312MS G++ 1.07K 2010-03-27 17:05:15 .
題目是說 給一張DAG，問你從A到B所有走法的路徑和%32768
V<=1000, E<=10^6
就topological sort + DP
//*********************************
#include<stdio.h>
#define MODE 32768
char name[100][25];
int stamp[1010],ttime,cost[1010],dp[1010],t,n,v,e,x,y,z;
bool visited[1010];
struct edge{
int j,cost;
edge *next;
}E[1000010],*V[1010];
void dfs(int n){
visited[n]=1;
for(edge *p=V[n]; p; p=p->next)
if(!visited[p->j])
dfs(p->j);
stamp[ttime++]=n;
}
int main(){
scanf("%d\n",&t);
for(int cnt=1;cnt<=t;cnt++){
printf("Game #%d\n",cnt);
//init
scanf("%d%d%d\n",&n,&v,&e);
for(int i=0;i<v;i++){
cost[i]=dp[i]=visited[i]=stamp[i]=0;
V[i]=NULL;
}
dp[0]=1;
ttime=0;
//input
for(int i=0;i<n;i++)
gets(name[i]);
for(int i=0;i<e;i++){
//printf("i=%d e=%d\n",i,e);
scanf("%d%d%d",&x,&y,&z);
edge *p=&E[i],*q=V[x];
V[x]=p; p->j=y; p->next=q; p->cost=z;
}
//time stamp
dfs(0);
//dp
for(int i=ttime-1;i>=0;i--){
int now=stamp[i];
for(edge *p=V[now]; p; p=p->next){
cost[p->j]+=cost[now]+ p->cost*dp[now];
cost[p->j]%=MODE;
dp[p->j]+=dp[now];
}
}
for(int i=0;i<n;i++)
printf("%s: %d\n",name[i],cost[i+1]);
}
}
題目是說 給一張DAG，問你從A到B所有走法的路徑和%32768
V<=1000, E<=10^6
就topological sort + DP
//*********************************
#include<stdio.h>
#define MODE 32768
char name[100][25];
int stamp[1010],ttime,cost[1010],dp[1010],t,n,v,e,x,y,z;
bool visited[1010];
struct edge{
int j,cost;
edge *next;
}E[1000010],*V[1010];
void dfs(int n){
visited[n]=1;
for(edge *p=V[n]; p; p=p->next)
if(!visited[p->j])
dfs(p->j);
stamp[ttime++]=n;
}
int main(){
scanf("%d\n",&t);
for(int cnt=1;cnt<=t;cnt++){
printf("Game #%d\n",cnt);
//init
scanf("%d%d%d\n",&n,&v,&e);
for(int i=0;i<v;i++){
cost[i]=dp[i]=visited[i]=stamp[i]=0;
V[i]=NULL;
}
dp[0]=1;
ttime=0;
//input
for(int i=0;i<n;i++)
gets(name[i]);
for(int i=0;i<e;i++){
//printf("i=%d e=%d\n",i,e);
scanf("%d%d%d",&x,&y,&z);
edge *p=&E[i],*q=V[x];
V[x]=p; p->j=y; p->next=q; p->cost=z;
}
//time stamp
dfs(0);
//dp
for(int i=ttime-1;i>=0;i--){
int now=stamp[i];
for(edge *p=V[now]; p; p=p->next){
cost[p->j]+=cost[now]+ p->cost*dp[now];
cost[p->j]%=MODE;
dp[p->j]+=dp[now];
}
}
for(int i=0;i<n;i++)
printf("%s: %d\n",name[i],cost[i+1]);
}
}
TIOJ 1237 砍了那些腳 Cut Many Legs [Greedy]
poao899 15648K 2009MS G++ 0.76K 2010-03-27 15:44:35 .
同UVa 10291不過測資加大(50 → 2*10^6)
是說這題題目頗難懂Q
以下是解釋小心雷
//***************************************
一個桌子會傾斜，就是因為把兩個平衡又高的腳連線當支點，
其中有一邊全部都是短腳而且佔其他所有桌腳重量一半( >= floor( (n-1)/2 ) )
Ex 1:
7
3 3 1 1 3 1 1
平衡 所以0
Ex 2:
6
3 1 1 3 3 3
不平衡所以全部砍到剩下1，答案是8
也就是找到一個數字是k，讓數列不能有連續(n-1)/2個數字小於k
//***************************************
#include<stdio.h>
int leg[4000010],n;
int l,r,mid,limit;
long long cut;
bool test(){
int s=0;
for(int i=0;i<n*2;i++){
s++;
if(leg[i]>mid)s=0;
if(s>=limit)return 0;
}
return 1;
}
int getint(){
int g=0,c=getchar(),s=1;
while(c==32||c==10||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
int main(){
while(n=getint()){
l=2147483647;r=-214748364;cut=0;
limit=(n-1)/2;
for(int i=0;i<n;i++){
leg[i+n]=leg[i]=getint();
if(leg[i]>r)r=leg[i];
if(leg[i]<l)l=leg[i];
}
while(l!=r){
mid=(l+r)/2;
if(test())l=mid+1;
else r=mid;
}
for(int i=0;i<n;i++)
if(leg[i]>l)cut+=leg[i]-l;
printf("%lld\n",cut);
}
}
同UVa 10291不過測資加大(50 → 2*10^6)
是說這題題目頗難懂Q
以下是解釋小心雷
//***************************************
一個桌子會傾斜，就是因為把兩個平衡又高的腳連線當支點，
其中有一邊全部都是短腳而且佔其他所有桌腳重量一半( >= floor( (n-1)/2 ) )
Ex 1:
7
3 3 1 1 3 1 1
平衡 所以0
Ex 2:
6
3 1 1 3 3 3
不平衡所以全部砍到剩下1，答案是8
也就是找到一個數字是k，讓數列不能有連續(n-1)/2個數字小於k
//***************************************
#include<stdio.h>
int leg[4000010],n;
int l,r,mid,limit;
long long cut;
bool test(){
int s=0;
for(int i=0;i<n*2;i++){
s++;
if(leg[i]>mid)s=0;
if(s>=limit)return 0;
}
return 1;
}
int getint(){
int g=0,c=getchar(),s=1;
while(c==32||c==10||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
int main(){
while(n=getint()){
l=2147483647;r=-214748364;cut=0;
limit=(n-1)/2;
for(int i=0;i<n;i++){
leg[i+n]=leg[i]=getint();
if(leg[i]>r)r=leg[i];
if(leg[i]<l)l=leg[i];
}
while(l!=r){
mid=(l+r)/2;
if(test())l=mid+1;
else r=mid;
}
for(int i=0;i<n;i++)
if(leg[i]>l)cut+=leg[i]-l;
printf("%lld\n",cut);
}
}
TIOJ 1529 邪惡的魔人姜姜 [Greedy]
poao899 15676K 6995MS G++ 1.37K 2010-03-27 13:12:37 .
說Greedy應該沒有捏到人吧(小聲
是說讓我爆炸的測資是
2
3.0 5.0
4.0 7.0
我會輸出50.000 應該很明顯問題在哪裡吧XDD
正確輸出是0.000
反正就是維持一個Heap
不過還是不習慣用STL...
小心浮點數誤差(?
//**************************************
#include<stdio.h>
#include<algorithm>
int n,top,allpow;
double pre_t,tored;
double hp;
int inline cmp(double a,double b){
double d=a-b;
if(d>10e-7)return -1;
else if(d<-10e-7)return 1;
return 0;
}
double min(double a,double b){
if(cmp(a,b)==1)return a;
return b;
}
struct loli{
double w,t;
bool operator<(const loli &b)const{
return cmp(t,b.t)==1 || !cmp(t,b.t)&&cmp(w,b.w)==-1;
}
void get(){
scanf("%lf%lf",&w,&t);
}
}l[500020];
struct ele{
double w,red;
bool operator<(const ele &b)const{
return cmp(w,b.w)==1;
}
}heap[500020];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
l[i].get();
std::sort(l,l+n);
for(int i=0;i<n;i++){
heap[top].w=l[i].w;
heap[top++].red=0;
std::push_heap(heap,heap+top);
tored=pre_t+l[i].w-l[i].t;
if(cmp(tored,0.0)==1)tored=0;
while(cmp(tored,0.0)==-1){
if(cmp(heap[0].w-heap[0].red , tored)==-1){
heap[0].red+=tored;
tored=0;
}else{
allpow++;
tored-=(heap[0].w-heap[0].red);
heap[0].red=heap[0].w=0;
std::pop_heap(heap,heap+top);top--;
}
}
pre_t = min( l[i].t , pre_t+l[i].w );
}
for(int i=0;i<top;i++)
if(cmp(heap[i].red,0)==-1)
hp+=heap[i].red*100/heap[i].w;
printf("%.3lf\n",hp+100.0*allpow);
}
說Greedy應該沒有捏到人吧(小聲
是說讓我爆炸的測資是
2
3.0 5.0
4.0 7.0
我會輸出50.000 應該很明顯問題在哪裡吧XDD
正確輸出是0.000
反正就是維持一個Heap
不過還是不習慣用STL...
小心浮點數誤差(?
//**************************************
#include<stdio.h>
#include<algorithm>
int n,top,allpow;
double pre_t,tored;
double hp;
int inline cmp(double a,double b){
double d=a-b;
if(d>10e-7)return -1;
else if(d<-10e-7)return 1;
return 0;
}
double min(double a,double b){
if(cmp(a,b)==1)return a;
return b;
}
struct loli{
double w,t;
bool operator<(const loli &b)const{
return cmp(t,b.t)==1 || !cmp(t,b.t)&&cmp(w,b.w)==-1;
}
void get(){
scanf("%lf%lf",&w,&t);
}
}l[500020];
struct ele{
double w,red;
bool operator<(const ele &b)const{
return cmp(w,b.w)==1;
}
}heap[500020];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
l[i].get();
std::sort(l,l+n);
for(int i=0;i<n;i++){
heap[top].w=l[i].w;
heap[top++].red=0;
std::push_heap(heap,heap+top);
tored=pre_t+l[i].w-l[i].t;
if(cmp(tored,0.0)==1)tored=0;
while(cmp(tored,0.0)==-1){
if(cmp(heap[0].w-heap[0].red , tored)==-1){
heap[0].red+=tored;
tored=0;
}else{
allpow++;
tored-=(heap[0].w-heap[0].red);
heap[0].red=heap[0].w=0;
std::pop_heap(heap,heap+top);top--;
}
}
pre_t = min( l[i].t , pre_t+l[i].w );
}
for(int i=0;i<top;i++)
if(cmp(heap[i].red,0)==-1)
hp+=heap[i].red*100/heap[i].w;
printf("%.3lf\n",hp+100.0*allpow);
}
2010年3月24日 星期三
TIOJ 1445 機器人組裝大賽 [次小生成樹]
poao899 13860K 1730MS G++ 1.90K 2010-03-24 19:14:56 .
次小生成樹。
利 用k小生成樹定理
變成 V^2(有點類似RMQ的東東) + E*O(1)(查詢)
被 long long 表= =
//*********************************
#include<cstdio>
#include<algorithm>
#define MAXV 1010
#define MAXE 500000
long long mst,mst2;
int n,m;
//gn
int getint(){
int g=0,c=getchar(),s=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
long long get64(){
long long g=0;int c=getchar(),s=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
//kruskal's necessity
struct ways{
int i,j;
long long c;
bool used;
void get(){
i=getint();j=getint();c=get64();
}
bool operator<(const ways &b)const{
return c<b.c;
}
}w[MAXE];
int root[MAXV];
int find(int a){
return root[a]==a?a:root[a]=find(root[a]);
}
int uni(int a,int b){
int ra=find(a),rb=find(b);
root[ra]=rb;
}
//DFS' necessity
struct edge{
int j;
long long c;
edge *next;
}e[MAXE],*v[MAXV];
void push(int i,int j,int c){
static int cnt=0;
edge *p=e+cnt++,*q;
p->j=j;p->c=c;
q=v[i];
v[i]=p;
p->next=q;
}
bool visited[MAXE],dfsed[MAXE];
long long dp[MAXV][MAXV];
int now;
void dfs(int n){
edge *p=v[n];
visited[n]=1;
for(;p!=NULL;p=p->next)
if(!visited[p->j]){
dp[now][p->j]=dp[now][n]>p->c ? dp[now][n] : p->c;
dfs(p->j);
}
}
int main(){
//input
n=getint();m=getint();
for(int i=0;i<m;i++)
w[i].get();
//kruskal
std::sort(w,w+m);
int edgeAdded=0;
for(int i=0;i<=n;i++)root[i]=i;
for(int i=0;i<m && edgeAdded<n-1;i++){
if(find(w[i].i)!=find(w[i].j)){
uni(w[i].i , w[i].j);
edgeAdded++;
mst+=w[i].c;
//build gragh
push(w[i].i,w[i].j,w[i].c);
push(w[i].j,w[i].i,w[i].c);
w[i].used=1;
}
}
//if can't find MST
if(edgeAdded!=n-1){puts("-1 -1");return 0;}
printf("%I64d ",mst);
//DFS, to find MST2
mst2=9223372036854775807LL;
for(int z=0;z<m;z++){
if(w[z].used)continue;
int x=w[z].i,y=w[z].j;
if(dfsed[x])
mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
else if(dfsed[y])
mst2=mst2<w[z].c-dp[y][x]?mst2:w[z].c-dp[y][x];
else{
//init
for(int i=0;i<MAXV;i++)
visited[i]=0;
now=x;dfsed[x]=1;
dfs(x);
mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
}
}
if(mst2==9223372036854775807LL)puts("-1");
else printf("%I64d\n",mst+mst2);
}
次小生成樹。
利 用k小生成樹定理
變成 V^2(有點類似RMQ的東東) + E*O(1)(查詢)
被 long long 表= =
//*********************************
#include<cstdio>
#include<algorithm>
#define MAXV 1010
#define MAXE 500000
long long mst,mst2;
int n,m;
//gn
int getint(){
int g=0,c=getchar(),s=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
long long get64(){
long long g=0;int c=getchar(),s=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-'){s=-1;c=getchar();}
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
//kruskal's necessity
struct ways{
int i,j;
long long c;
bool used;
void get(){
i=getint();j=getint();c=get64();
}
bool operator<(const ways &b)const{
return c<b.c;
}
}w[MAXE];
int root[MAXV];
int find(int a){
return root[a]==a?a:root[a]=find(root[a]);
}
int uni(int a,int b){
int ra=find(a),rb=find(b);
root[ra]=rb;
}
//DFS' necessity
struct edge{
int j;
long long c;
edge *next;
}e[MAXE],*v[MAXV];
void push(int i,int j,int c){
static int cnt=0;
edge *p=e+cnt++,*q;
p->j=j;p->c=c;
q=v[i];
v[i]=p;
p->next=q;
}
bool visited[MAXE],dfsed[MAXE];
long long dp[MAXV][MAXV];
int now;
void dfs(int n){
edge *p=v[n];
visited[n]=1;
for(;p!=NULL;p=p->next)
if(!visited[p->j]){
dp[now][p->j]=dp[now][n]>p->c ? dp[now][n] : p->c;
dfs(p->j);
}
}
int main(){
//input
n=getint();m=getint();
for(int i=0;i<m;i++)
w[i].get();
//kruskal
std::sort(w,w+m);
int edgeAdded=0;
for(int i=0;i<=n;i++)root[i]=i;
for(int i=0;i<m && edgeAdded<n-1;i++){
if(find(w[i].i)!=find(w[i].j)){
uni(w[i].i , w[i].j);
edgeAdded++;
mst+=w[i].c;
//build gragh
push(w[i].i,w[i].j,w[i].c);
push(w[i].j,w[i].i,w[i].c);
w[i].used=1;
}
}
//if can't find MST
if(edgeAdded!=n-1){puts("-1 -1");return 0;}
printf("%I64d ",mst);
//DFS, to find MST2
mst2=9223372036854775807LL;
for(int z=0;z<m;z++){
if(w[z].used)continue;
int x=w[z].i,y=w[z].j;
if(dfsed[x])
mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
else if(dfsed[y])
mst2=mst2<w[z].c-dp[y][x]?mst2:w[z].c-dp[y][x];
else{
//init
for(int i=0;i<MAXV;i++)
visited[i]=0;
now=x;dfsed[x]=1;
dfs(x);
mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
}
}
if(mst2==9223372036854775807LL)puts("-1");
else printf("%I64d\n",mst+mst2);
}
2010年3月8日 星期一
TIOJ 1575 欸西國的欸西M大賽(Accepted) [97校內 prob6]
poao899 36288K 16822MS G++ 1.68K 2010-03-08 17:25:08 .
題意是這樣的，給你一棵樹，n<10^6，選出k個點(k<10^6)，
請問對於每個樹上的點，要走到這k個點的最短距離的最大值是多少？
Hint:
對答案二分搜，
再從樹葉Greedy
噢對了記得要寫stack
//****************************************
#include<stdio.h>
#define MAXN 2000100
struct edge{
int j;
edge *next;
}*v[MAXN],e[MAXN*2],*ptr,*nowe;
void set(int i,int j){
static int cnt=0;
nowe=&e[cnt++];
ptr=v[i];
v[i]=nowe;
nowe->j=j;
nowe->next=ptr;
}
int ar[MAXN],top;
int dp[MAXN],dmax,dnow;
int max[MAXN],min[MAXN],fa[MAXN];
int n,m,k,a,b;
bool can,visited[MAXN];
bool chk(){
can=1;dnow=0;
for(int i=0;i<=n;i++)
visited[i]=0;
ar[1]=top=1;
while(top){
int now=ar[top];
if(!can)return 0;
if(now>0){
max[now]=-1;min[now]=0;
visited[now]=1;
dp[now]=0;
ar[top]=-now;
int max=-1,min=0;
for(edge *ptr=v[now];ptr;ptr=ptr->next){
if(visited[ptr->j]){
fa[now]=ptr->j;
continue;
}
ar[++top]=ptr->j;
}
}else{
now=-now;
if(max[now]>=dmax-1){
dp[now]=-dmax;
dnow++;
if(dnow>k)
can=0;
}
else if(max[now]<0){
if(min[now]<0)
dp[now]=min[now]+1;
}
else{
if(-min[now]-2>=max[now])
dp[now]=min[now]+1;
else
dp[now]=max[now]+1;
}
if(dp[now]>max[fa[now]])
max[fa[now]]=dp[now];
if(dp[now]<min[fa[now]])
min[fa[now]]=dp[now];
top--;
}
}
if(dp[1]>0)dnow++;
return can&&dnow<=k;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
if(n==k){puts("0");return 0;}
else if(k==0){printf("%d\n",n-1);return 0;}
if(n-1!=m)for(;;)puts("XDD");
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
set(a,b);
set(b,a);
}
int _l=0,_r=n;
while(_l!=_r){
dmax=(_l+_r)/2;
if(!chk())
_l=dmax+1;
else _r=dmax;
}
printf("%d\n",_l);
}
題意是這樣的，給你一棵樹，n<10^6，選出k個點(k<10^6)，
請問對於每個樹上的點，要走到這k個點的最短距離的最大值是多少？
Hint:
對答案二分搜，
再從樹葉Greedy
噢對了記得要寫stack
//****************************************
#include<stdio.h>
#define MAXN 2000100
struct edge{
int j;
edge *next;
}*v[MAXN],e[MAXN*2],*ptr,*nowe;
void set(int i,int j){
static int cnt=0;
nowe=&e[cnt++];
ptr=v[i];
v[i]=nowe;
nowe->j=j;
nowe->next=ptr;
}
int ar[MAXN],top;
int dp[MAXN],dmax,dnow;
int max[MAXN],min[MAXN],fa[MAXN];
int n,m,k,a,b;
bool can,visited[MAXN];
bool chk(){
can=1;dnow=0;
for(int i=0;i<=n;i++)
visited[i]=0;
ar[1]=top=1;
while(top){
int now=ar[top];
if(!can)return 0;
if(now>0){
max[now]=-1;min[now]=0;
visited[now]=1;
dp[now]=0;
ar[top]=-now;
int max=-1,min=0;
for(edge *ptr=v[now];ptr;ptr=ptr->next){
if(visited[ptr->j]){
fa[now]=ptr->j;
continue;
}
ar[++top]=ptr->j;
}
}else{
now=-now;
if(max[now]>=dmax-1){
dp[now]=-dmax;
dnow++;
if(dnow>k)
can=0;
}
else if(max[now]<0){
if(min[now]<0)
dp[now]=min[now]+1;
}
else{
if(-min[now]-2>=max[now])
dp[now]=min[now]+1;
else
dp[now]=max[now]+1;
}
if(dp[now]>max[fa[now]])
max[fa[now]]=dp[now];
if(dp[now]<min[fa[now]])
min[fa[now]]=dp[now];
top--;
}
}
if(dp[1]>0)dnow++;
return can&&dnow<=k;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
if(n==k){puts("0");return 0;}
else if(k==0){printf("%d\n",n-1);return 0;}
if(n-1!=m)for(;;)puts("XDD");
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
set(a,b);
set(b,a);
}
int _l=0,_r=n;
while(_l!=_r){
dmax=(_l+_r)/2;
if(!chk())
_l=dmax+1;
else _r=dmax;
}
printf("%d\n",_l);
}
2010年3月4日 星期四
TIOJ 1202 重疊的天際線
nolonger 1104K 249MS G++ 1.79K 2010-03-04 21:14:24 .
蝴蝶的1k一定是因為另有正解！
怪噁心的Heap= =
#include<stdio.h>
#include<algorithm>
#define MAX 30010
int n,pos,ary[MAX*2],cnt,np,bcnt;
bool fl;
struct skyline{
int hei[MAX],pos[MAX],rear;
void init(){
rear=hei[0]=0;
pos[0]=1;
}
void push(int x,int y){
if(pos[rear]==x){
if(hei[rear]<y)
hei[rear]=y;
}
else if(hei[rear]!=y){
hei[++rear]=y;
pos[rear]=x;
}
}
}s;
struct ele{
int l,r,h;
bool operator<(const ele &b)const{
return h<b.h;
}
inline void get(){
scanf("%d%d%d",&l,&h,&r);
ary[cnt++]=l;
ary[cnt++]=r;
}
}e[MAX];
bool cmp(ele a,ele b){
return a.l<b.l;
}
struct heap{
ele ar[MAX],t;
int rear;
void ch(int a,int b){
t=ar[a];
ar[a]=ar[b];
ar[b]=t;
}
void upset(int n){
if(n<2||n>=rear)return;
int t=n/2;
if(ar[t]<ar[n]){
ch(t,n);
upset(t);
}
}
void downset(int n){
if(n<1||n>=rear)return;
int t=n<<1,opt;
if(t<rear&&ar[n]<ar[t]){
opt=t+1<rear&&ar[t]<ar[t+1];
ch(t+opt,n);
downset(t+opt);
}
else if(t+1<rear&&ar[n]<ar[t+1]){
ch(t+1,n);
downset(t+1);
}
}
void push(ele a){
ar[rear]=a;
upset(rear++);
}
void pop(){
if(rear<2)return;
ch(1,--rear);
downset(1);
}
}h;
int main(){
while(scanf("%d",&n),n){
s.init();
h.rear=1;
bcnt=cnt=np=fl=0;
for(int i=0;i<n;i++)
e[i].get();
std::sort(e,e+n,cmp);
std::sort(ary,ary+cnt);
e[n].l=0;e[n].r=ary[cnt-1]+1;e[n].h=0;
h.push(e[n]);
for(int i=0;i<cnt;){
pos=ary[i];
for(;bcnt<n&&e[bcnt].l<=pos;bcnt++)
h.push(e[bcnt]);
while(h.ar[1].r<=pos)
h.pop();
s.push(pos,h.ar[1].h);
while(i<cnt&&ary[i]==pos)i++;
}
for(int i=0;i<=s.rear;i++){
if(s.pos[i]==1&&s.hei[i]==0)continue;
if(fl)putchar(32);
printf("%d %d",s.pos[i],s.hei[i]);
fl=1;
}
putchar('\n');
}
}
蝴蝶的1k一定是因為另有正解！
怪噁心的Heap= =
#include<stdio.h>
#include<algorithm>
#define MAX 30010
int n,pos,ary[MAX*2],cnt,np,bcnt;
bool fl;
struct skyline{
int hei[MAX],pos[MAX],rear;
void init(){
rear=hei[0]=0;
pos[0]=1;
}
void push(int x,int y){
if(pos[rear]==x){
if(hei[rear]<y)
hei[rear]=y;
}
else if(hei[rear]!=y){
hei[++rear]=y;
pos[rear]=x;
}
}
}s;
struct ele{
int l,r,h;
bool operator<(const ele &b)const{
return h<b.h;
}
inline void get(){
scanf("%d%d%d",&l,&h,&r);
ary[cnt++]=l;
ary[cnt++]=r;
}
}e[MAX];
bool cmp(ele a,ele b){
return a.l<b.l;
}
struct heap{
ele ar[MAX],t;
int rear;
void ch(int a,int b){
t=ar[a];
ar[a]=ar[b];
ar[b]=t;
}
void upset(int n){
if(n<2||n>=rear)return;
int t=n/2;
if(ar[t]<ar[n]){
ch(t,n);
upset(t);
}
}
void downset(int n){
if(n<1||n>=rear)return;
int t=n<<1,opt;
if(t<rear&&ar[n]<ar[t]){
opt=t+1<rear&&ar[t]<ar[t+1];
ch(t+opt,n);
downset(t+opt);
}
else if(t+1<rear&&ar[n]<ar[t+1]){
ch(t+1,n);
downset(t+1);
}
}
void push(ele a){
ar[rear]=a;
upset(rear++);
}
void pop(){
if(rear<2)return;
ch(1,--rear);
downset(1);
}
}h;
int main(){
while(scanf("%d",&n),n){
s.init();
h.rear=1;
bcnt=cnt=np=fl=0;
for(int i=0;i<n;i++)
e[i].get();
std::sort(e,e+n,cmp);
std::sort(ary,ary+cnt);
e[n].l=0;e[n].r=ary[cnt-1]+1;e[n].h=0;
h.push(e[n]);
for(int i=0;i<cnt;){
pos=ary[i];
for(;bcnt<n&&e[bcnt].l<=pos;bcnt++)
h.push(e[bcnt]);
while(h.ar[1].r<=pos)
h.pop();
s.push(pos,h.ar[1].h);
while(i<cnt&&ary[i]==pos)i++;
}
for(int i=0;i<=s.rear;i++){
if(s.pos[i]==1&&s.hei[i]==0)continue;
if(fl)putchar(32);
printf("%d %d",s.pos[i],s.hei[i]);
fl=1;
}
putchar('\n');
}
}
TIOJ 1231 寵物雞問題 (TOI 2005) [Greedy]
poao899 1168K 325MS G++ 1.13K 2010-03-04 18:16:59 .
Greedy.
是說竟然寫出了O(n)的Heap= =
#include<stdio.h>
#include<algorithm>
#define MAX 100010
int n,ed,weight,cnt;
struct heap{
int ar[MAX];
int rear;
void ch(int a,int b){
int t=ar[a];
ar[a]=ar[b];
ar[b]=t;
}
void upset(int n){
if(n<2||n>=rear)return;
int t=n>>1;
if(t>0&&ar[t]<ar[n]){
ch(t,n);
upset(t);
}
}
void downset(int n){
if(n<1||n>=rear)return;
int t=n<<1,opt;
if(t<rear&&ar[n]<ar[t]){
opt=t+1<rear&&ar[t]<ar[t+1];
ch(t+opt,n);
downset(t+opt);
}
else if(t+1<rear&&ar[n]<ar[t+1]){
ch(t+1,n);
downset(t+1);
}
}
void push(int n){
ar[rear++]=n;
upset(rear-1);
}
int pop(){
int t=ar[1];
ch(1,--rear);
downset(1);
return t;
}
}h;
struct seg{
int cal,t;
void get(){
scanf("%d%d",&cal,&t);
}
bool operator<(const seg &b)const{
return t>b.t;
}
}s[MAX];
int main(){
scanf("%d",&n);
cnt=0;h.rear=1;
for(int i=0;i<n;i++)
s[i].get();
scanf("%d",&ed);
std::sort(s,s+n);
for(int i=ed;i>0;i--){
for(;cnt<n&&s[cnt].t>=i;cnt++){
h.push(s[cnt].cal);
}
if(h.rear>1)
weight+=h.pop();
else weight--;
}
printf("%d\n",weight);
}
Greedy.
是說竟然寫出了O(n)的Heap= =
#include<stdio.h>
#include<algorithm>
#define MAX 100010
int n,ed,weight,cnt;
struct heap{
int ar[MAX];
int rear;
void ch(int a,int b){
int t=ar[a];
ar[a]=ar[b];
ar[b]=t;
}
void upset(int n){
if(n<2||n>=rear)return;
int t=n>>1;
if(t>0&&ar[t]<ar[n]){
ch(t,n);
upset(t);
}
}
void downset(int n){
if(n<1||n>=rear)return;
int t=n<<1,opt;
if(t<rear&&ar[n]<ar[t]){
opt=t+1<rear&&ar[t]<ar[t+1];
ch(t+opt,n);
downset(t+opt);
}
else if(t+1<rear&&ar[n]<ar[t+1]){
ch(t+1,n);
downset(t+1);
}
}
void push(int n){
ar[rear++]=n;
upset(rear-1);
}
int pop(){
int t=ar[1];
ch(1,--rear);
downset(1);
return t;
}
}h;
struct seg{
int cal,t;
void get(){
scanf("%d%d",&cal,&t);
}
bool operator<(const seg &b)const{
return t>b.t;
}
}s[MAX];
int main(){
scanf("%d",&n);
cnt=0;h.rear=1;
for(int i=0;i<n;i++)
s[i].get();
scanf("%d",&ed);
std::sort(s,s+n);
for(int i=ed;i>0;i--){
for(;cnt<n&&s[cnt].t>=i;cnt++){
h.push(s[cnt].cal);
}
if(h.rear>1)
weight+=h.pop();
else weight--;
}
printf("%d\n",weight);
}
2010年3月3日 星期三
TIOJ 1155 4.經濟編碼 [93全國賽(prob 4)]
68011 poao899 1155 Accepted 12K 75MS G++ 0.96K 2010-03-03 22:41:27 .
噢哈好久沒寫TIOJ了XD
單純Heap這樣
是說 Heap又長得跟之前不一樣了XD
#include<stdio.h>
#define MAX 100010
struct heap{
double ar[MAX];
int rear;
inline void change(int n,int m){
double t=ar[n];
ar[n]=ar[m];
ar[m]=t;
}
void upset(int n){
if(n<2 || n>=rear)return;
int t=n/2;
if(ar[t]>ar[n]){
change(t,n);
upset(t);
}
}
void downset(int n){
if(n<1 || n>=rear)return;
int t=n*2;
for(int i=0;i<2;i++)
if(t+i<rear&&ar[n]>ar[t+i]){
change(t+i,n);
downset(t+i);
}
}
inline void push(double a){
ar[rear]=a;
upset(rear++);
}
inline double pop(){
if(rear==1)return 0;
double x=ar[1];
change(1,--rear);
downset(1);
return x;
}
}h;
int n;
char buffer[100];
double total,t;
int main(){
gets(buffer);
sscanf(buffer,"%d",&n);
h.rear=1;
while(n--){
gets(buffer);
sscanf(buffer,"%*c %lf",&t);
h.push(t);
}
for(;;){
t=h.pop()+h.pop();
if(h.rear==1)break;
total+=t;
h.push(t);
}
printf("%.2lf\n",total+t);
//main();
}
噢哈好久沒寫TIOJ了XD
單純Heap這樣
是說 Heap又長得跟之前不一樣了XD
#include<stdio.h>
#define MAX 100010
struct heap{
double ar[MAX];
int rear;
inline void change(int n,int m){
double t=ar[n];
ar[n]=ar[m];
ar[m]=t;
}
void upset(int n){
if(n<2 || n>=rear)return;
int t=n/2;
if(ar[t]>ar[n]){
change(t,n);
upset(t);
}
}
void downset(int n){
if(n<1 || n>=rear)return;
int t=n*2;
for(int i=0;i<2;i++)
if(t+i<rear&&ar[n]>ar[t+i]){
change(t+i,n);
downset(t+i);
}
}
inline void push(double a){
ar[rear]=a;
upset(rear++);
}
inline double pop(){
if(rear==1)return 0;
double x=ar[1];
change(1,--rear);
downset(1);
return x;
}
}h;
int n;
char buffer[100];
double total,t;
int main(){
gets(buffer);
sscanf(buffer,"%d",&n);
h.rear=1;
while(n--){
gets(buffer);
sscanf(buffer,"%*c %lf",&t);
h.push(t);
}
for(;;){
t=h.pop()+h.pop();
if(h.rear==1)break;
total+=t;
h.push(t);
}
printf("%.2lf\n",total+t);
//main();
}
訂閱：
文章 (Atom)