发现现在做比赛越来越窝囊了。。。一点状态没有
还是流水账一下
pku1894 Alternative Scale of Notation记得秦九昭算法的思想？不说了，不断地提取系数
1
Source Code
2
3Problem: 1894 User: yzhw
4Memory: 2524K Time: 5719MS
5Language: Java Result: Accepted
6Source Code
7import java.math.*;
8import java.io.*;
9import java.util.*;
10public class Main 
{
11
public static void main(String[] args) throws IOException{
12
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
13 BigInteger b=new BigInteger(in.readLine());
14 BigInteger num=new BigInteger(in.readLine());
15 if(num.equals(BigInteger.ZERO))
16 {
17 System.out.println();
18 return;
19
}
20 Stack<BigInteger> ans=new Stack<BigInteger>();
21 while(!num.equals(BigInteger.ZERO))
22 {
23 if(num.mod(b).equals(BigInteger.ZERO))
24 ans.push(b);
25 else ans.push(num.mod(b));
26 num=num.add(ans.peek().negate());
27 num=num.divide(b);
28 }
29 while(!ans.isEmpty())
30 System.out.print(ans.pop());
31 System.out.println();
32
33 }
34
35
}看输出以为是搜索，结果果断的TLE。。CW神牛说了一种分层+二分网络流方案，觉得可以。改天写好补上
pku1896 Code Formatting注意换行的时候，当;和{在一起的时候;的换行特殊考虑。。设置一个标记事后换行就可以了。。
1
# include <stdio.h>
2int endl=0,f=0;
3void print()
4{
5
int i;
6 if(endl)
7
{
8 endl=0;
9 putchar('\n');
10 for(i=0;i<4*f;i++) putchar(' ');
11
}
12
}
13int main()
14{
15 //freopen("ans.txt","w",stdout);
16 char c;
17 int flag=0;
18 while(scanf("%c",&c)!=EOF)
19 switch(c)
20 {
21 case ' ':
22 break;
23 case 13:
24 break;
25 case 10:
26 break;
27 case 9:
28 break;
29 case '{':
30 print();
31 if(!flag)
32 {
33 putchar('{');
34 flag=1;
35 endl=1;
36 }
37 else
38 {
39 putchar(' ');
40 putchar('{');
41 }
42 endl=1;
43 f++;
44 break;
45 case '}':
46 f--;
47 endl=1;
48 print();
49 putchar('}');
50 break;
51 case ';':
52 putchar(';');
53 endl=1;
54 break;
55 case ',':
56 print();
57 putchar(',');
58 putchar(' ');
59 break;
60 default:
61 print();
62 putchar(c);
63 break;
64 };
65 //system("pause");
66 return 0;
67}很简单的一题，枚举就可以。注意细节，总长度为(n-1)*newsizeB+sizeB
阴险的数据？当n=1?
1# include <stdio.h>
2int main()
3{
4 int n,i,bit=33,A=-1,B=-1;
5 long long res=0xfffffffffffffffll,sp,sq;
6 scanf("%d%lld%lld",&n,&sp,&sq);
7 if(n==1)
8 {
9 printf("%d 0 0\n",sq);
10 return 0;
11 }
12 for(i=0;i<=bit;i++)
13 {
14 if(sp+(sp<<i)<sq) continue;
15 int b=0;
16 while(((sp+(sp<<i))>>b)>=sq) b++;
17 b--;
18 if(((sp*(n-1)+((sp*(n-1))<<i))>>b)+sq<res)
19 res=((sp*(n-1)+((sp*(n-1))<<i))>>b)+sq,A=i,B=b;
20 }
21 printf("%lld %d %d\n",res,A,B);
22 //system("pause");
23 return 0;
24}我不想说什么，POJ的SPJ真是诡异啊。。。。。我原来写了个程序，自己写了个测试程序测试了下，没问题，一提交，WA，超级无奈之下，打了1M的表，提交上去，A。。。说下，不要随机化，动态逼近即可。。先设置2个点，一头一尾，肯定最小。然后试图调整达到最大值；调整不了再插入点。就是这样。。
1 # include <cstdio>
2 # include <cmath>
3 # include <vector>
4 # define N 1000
5 using namespace std;
6 # define abs(a) ((a)<0?-(a):(a))
7 int num,now;
8 int data[1001];
9 vector<int> ans;
10 bool upper()
11 {
12 for(int i=0;i<ans.size();i++)
13 for(int j=i+1;j<ans.size();j++)
14 if(now-data[ans[i]]-data[ans[j]]+data[ans[i]+1]+data[ans[j]-1]>now&&now-data[ans[i]]-data[ans[j]]+data[ans[i]+1]+data[ans[j]-1]<=num)
15 {
16 now=now-data[ans[i]]-data[ans[j]]+data[ans[i]+1]+data[ans[j]-1];
17 ans[i]++;
18 ans[j]--;
19 return true;
20 }
21 else if(ans[i]>1&&ans[j]<1000&&now-data[ans[i]]-data[ans[j]]+data[ans[i]-1]+data[ans[j]+1]>now&&now-data[ans[i]]-data[ans[j]]+data[ans[i]-1]+data[ans[j]+1]<=num)
22 {
23 now=now-data[ans[i]]-data[ans[j]]+data[ans[i]-1]+data[ans[j]+1];
24 ans[i]--;
25 ans[j]++;
26 return true;
27 }
28 return false;
29 }
30 bool lower()
31 {
32 for(int i=0;i<ans.size();i++)
33 for(int j=i+1;j<ans.size();j++)
34 if(now-data[ans[i]]-data[ans[j]]+data[ans[i]+1]+data[ans[j]-1]<now)
35 {
36 now=now-data[ans[i]]-data[ans[j]]+data[ans[i]+1]+data[ans[j]-1];
37 ans[i]++;
38 ans[j]--;
39 return true;
40 }
41 else if(ans[i]>1&&ans[j]<1000&&now-data[ans[i]]-data[ans[j]]+data[ans[i]-1]+data[ans[j]+1]<now)
42 {
43 now=now-data[ans[i]]-data[ans[j]]+data[ans[i]-1]+data[ans[j]+1];
44 ans[i]--;
45 ans[j]++;
46 return true;
47 }
48 return false;
49 }
50 void spilt()
51 {
52 for(int i=0;i<ans.size();i++)
53 if(ans[i]>1)
54 {
55 now-=data[ans[i]];
56 now+=data[ans[i]/2];
57 now+=data[ans[i]-ans[i]/2];
58 ans.push_back(ans[i]/2);
59 ans[i]=ans[i]-ans[i]/2;
60 return;
61 }
62 }
63 int cal()
64 {
65 int tmp=0;
66 for(int i=0;i<ans.size();i++)
67 tmp+=data[ans[i]];
68 return tmp;
69
70 }
71 int main()
72 {
73 //scanf("%lf",&num);
74 for(int i=1;i<=1000;i++)
75 data[i]=-i*log2(i/1000.0)+1e-6;
76 double tnum;
77 scanf("%lf",&tnum);
78 num=tnum*1000+1e-6;
79 if(num==0)
80 {
81 printf("\n");
82 return 0;
83 }
84 ans.clear();
85 now=data[1]+data[999];
86 ans.push_back(1);
87 ans.push_back(999);
88 while(abs(num-now)>1)
89 {
90 while(num>now&upper());
91 if(num>now)
92 {
93 spilt();
94 while(now>num) lower();
95 }
96 }
97 char map[]={"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789. "};
98 int p=0;
99 for(int i=0;i<ans.size();i++)
100 {
101 while(ans[i]--)
102 putchar(map[p]);
103 p++;
104 }
105 putchar('\n');
106 return 0;
107}
pku1899 Farmer Bill's Problem无限迭代+并查集。复杂度？n2logn
1# include <stdio.h>
2# include <string.h>
3# include <stdbool.h>
4# define N 105
5# define max(a,b) ((a)>(b)?(a):(b))
6# define min(a,b) ((a)<(b)?(a):(b))
7# define in(xx,yy,pp) (xx>=data[pp].x1&&xx<=data[pp].x2&&yy>=data[pp].y1&&yy<=data[pp].y2)
8# define linked(a,b) (in(data[a].x1,data[a].y1,b)||in(data[a].x2,data[a].y2,b)||in(data[a].x2,data[a].y1,b)||in(data[a].x1,data[a].y2,b)|| in(data[b].x1,data[b].y1,a)||in(data[b].x2,data[b].y2,a)||in(data[b].x1,data[b].y2,a)||in(data[b].x2,data[b].y1,a))
9struct node
10{
11 int x1,x2,y1,y2;
12}data[N],tmp[N];
13int x,y,n,c;
14int pre[N];
15bool used[N];
16int find(int pos)
17{
18 if(pre[pos]==pos) return pos;
19 else return pre[pos]=find(pre[pos]);
20}
21int main()
22{
23 int i,j;
24 scanf("%d%d%d",&x,&y,&n);
25 for(i=0;i<n;i++)
26 {
27 int tx,ty,r;
28 scanf("%d%d%d",&tx,&ty,&r);
29 data[i].x1=tx-r;
30 data[i].x2=tx+r;
31 data[i].y1=ty-r;
32 data[i].y2=ty+r;
33 }
34 while(true)
35 {
36 bool flag=false;
37 for(i=0;i<n;i++) pre[i]=i;
38 memset(used,false,sizeof(used));
39 for(i=0;i<n;i++)
40 for(j=i+1;j<n;j++)
41 if(linked(i,j))
42 pre[find(i)]=find(j),flag=true;
43 c=0;
44 for(i=0;i<n;i++)
45 if(!used[find(i)])
46 {
47 struct node t;
48 t=data[i];
49 used[find(i)]=true;
50 for(j=i+1;j<n;j++)
51 if(find(i)==find(j))
52 {
53 t.x1=min(t.x1,data[j].x1);
54 t.x2=max(t.x2,data[j].x2);
55 t.y1=min(t.y1,data[j].y1);
56 t.y2=max(t.y2,data[j].y2);
57 }
58 tmp[c++]=t;
59 }
60 memcpy(data,tmp,sizeof(data));
61 n=c;
62 if(!flag) break;
63 }
64 int ans=x*y;
65 for(i=0;i<n;i++)
66 ans-=(data[i].x2-data[i].x1)*(data[i].y2-data[i].y1);
67 printf("%d\n",ans);
68 //system("pause");
69 return 0;
70}枚举所有可能的半径+离散化+树状数组统计
1# include <cstdio>
2# include <algorithm>
3# include <cstring>
4# include <cmath>
5using namespace std;
6# define lowbit(bit) (bit&-bit)
7# define dis(a,b) (((long long)p[(a)].x-p[(b)].x)*((long long)p[(a)].x-p[(b)].x)+\
8 ((long long)p[(a)].y-p[(b)].y)*((long long)p[(a)].y-p[(b)].y)+\
9 ((long long)p[(a)].z-p[(b)].z)*((long long)p[(a)].z-p[(b)].z))
10# define N 1005
11long long s[N*N];
12long long ts[N];
13int c=0,n,tc;
14
15struct node
16{
17 int x,y,z;
18 bool type;
19}p[N];
20int arr[N*N];
21int tarr[N];
22
23void add(int pos,int val,int a[],int end)
24{
25 pos++;
26 while(pos<=end)
27 a[pos]+=val,pos+=lowbit(pos);
28}
29int sum(int pos,int a[])
30{
31 pos++;
32 int res=0;
33 while(pos>0)
34 res+=a[pos],pos-=lowbit(pos);
35 return res;
36}
37int main()
38{
39 scanf("%d",&n);
40 for(int i=0;i<n;i++)
41 scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].z,&p[i].type);
42 s[c++]=0;
43 for(int i=0;i<n;i++)
44 for(int j=i+1;j<n;j++)
45 s[c++]=dis(i,j);
46 sort(s,s+c);
47 c=unique(s,s+c)-s;
48 memset(arr,0,sizeof(arr));
49 for(int i=0;i<n;i++)
50 {
51 tc=0;
52 memset(tarr,0,sizeof(tarr));
53 for(int j=0;j<n;j++)
54 ts[tc++]=dis(i,j);
55 sort(ts,ts+tc);
56 tc=unique(ts,ts+tc)-ts;
57 for(int j=0;j<n;j++)
58 if(p[i].type==p[j].type)
59 add(lower_bound(ts,ts+tc,dis(i,j))-ts,1,tarr,tc);
60 else
61 add(lower_bound(ts,ts+tc,dis(i,j))-ts,-1,tarr,tc);
62 for(int j=0;j<tc-1;j++)
63 if(sum(lower_bound(ts,ts+tc,ts[j])-ts,tarr)<0)
64 {
65 add(lower_bound(s,s+c,ts[j])-s,1,arr,c);
66 add(lower_bound(s,s+c,ts[j+1])-s,-1,arr,c);
67 }
68 if(sum(lower_bound(ts,ts+tc,ts[tc-1])-ts,tarr)<0)
69 add(lower_bound(s,s+c,ts[tc-1])-s,1,arr,c);
70
71 }
72 int res=-1;
73 double ans=-1;
74 for(int i=0;i<c;i++)
75 if(sum(i,arr)>res)
76 res=sum(i,arr),ans=s[i];
77 printf("%d\n%.4f\n",res,sqrt(ans));
78 return 0;
79}1e8的搜索+位运算，真是蛋疼，搜索无敌啊。。
1import java.util.*;
2import java.io.*;
3
4public class Main {
5 private static int best_bones;
6 private static int best_len;
7 private static int n;
8
9 private static int[] patterns;
10
11 private static void find(int joints, int bones, int len, int i) {
12 if (joints == 0 && len > best_len) {
13 best_bones = bones;
14 best_len = len;
15 }
16 if (len + (n - i) <= best_len || i >= n)
17 return;
18 find(joints, bones, len, i + 1);
19 find(joints ^ patterns[i], bones | (1 << i), len + 1, i + 1);
20 }
21
22 public static void main(String[] args) throws IOException {
23 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
24 n = Integer.parseInt(in.readLine().trim());
25 patterns = new int[n];
26 for (int i = 0; i < n; i++) {
27 String s = in.readLine();
28 for (int j = s.length(); --j >= 0;)
29 patterns[i] |= 1 << (s.charAt(j) - 'A');
30 }
31
32
33 find(0, 0, 0, 0);
34
35
36 System.out.println(best_len);
37 for (int i = 0; i < n; i++)
38 if ((best_bones & (1 << i)) != 0)
39 System.out.print((i + 1) + " ");
40
41 }
42}二分匹配的好题，在延伸独立轨时的特点。最终转化为求SSG
1# include <cstdio>
2# include <cstring>
3# include <vector>
4# include <algorithm>
5# include <cstdlib>
6using namespace std;
7# define N 4005
8# define M 300000
9int n;
10int g[N],nxt[M],v[M],c=0;
11int dfn=0,stack[N],top=0,low[N];
12vector<int> ans[N];
13vector<int> ori[N];
14vector<int> tmp1,tmp2;
15void dfs(int pos)
16{
17 if(low[pos]!=-1) return;
18 int cur=dfn++;
19 low[pos]=cur;
20 stack[top++]=pos;
21 for(int p=g[pos];p!=-1;p=nxt[p])
22 {
23 dfs(v[p]);
24 if(low[v[p]]<cur) cur=low[v[p]];
25 }
26 if(cur<low[pos]) low[pos]=cur;
27 else
28 {
29 tmp1.clear();
30 tmp2.clear();
31 do
32 {
33 top--;
34 if(stack[top]<n) tmp1.push_back(stack[top]);
35 else tmp2.push_back(stack[top]-n);
36 low[stack[top]]=2*n;
37 }while(stack[top]!=pos);
38 for(int i=0;i<tmp1.size();i++)
39 for(int j=0;j<tmp2.size();j++)
40 if(binary_search(ori[tmp1[i]].begin(),ori[tmp1[i]].end(),tmp2[j]))
41 ans[tmp1[i]].push_back(tmp2[j]);
42 }
43}
44void insert(int s,int e)
45{
46 v[c]=e;
47 nxt[c]=g[s];
48 g[s]=c++;
49}
50int main()
51{
52 scanf("%d",&n);
53 memset(g,-1,sizeof(g));
54 for(int i=0;i<n;i++)
55 {
56 int k,t;
57 scanf("%d",&k);
58 ans[i].clear();
59 ori[i].clear();
60 while(k--)
61 {
62 scanf("%d",&t);
63 insert(i,t-1+n);
64 ori[i].push_back(t-1);
65 }
66 sort(ori[i].begin(),ori[i].end());
67 }
68 for(int i=0;i<n;i++)
69 {
70 int t;
71 scanf("%d",&t);
72 insert(t-1+n,i);
73 }
74 memset(low,-1,sizeof(low));
75 for(int i=0;i<n;i++)
76 dfs(i);
77 for(int i=0;i<n;i++)
78 {
79 sort(ans[i].begin(),ans[i].end());
80 printf("%d",ans[i].size());
81 for(int j=0;j<ans[i].size();j++)
82 printf(" %d",ans[i][j]+1);
83 printf("\n");
84 }
85 // system("pause");
86 return 0;
87}