吐槽：
1. 大家可能會疑惑544的總結呢。。。 因為544掛0了，就不寫總結了額 - -
2. 周末參加東北賽，祝自己好運
3. 漲了166pt真是耗人品
4. 下周數電實驗答辯(20頁的報告我擦)+電子技術考試，真是煩啊！！！！
5. 最后一個賽季，fighting!!! 要么出線要么滾蛋...
其實我在房間實在太弱了 - -
275pt:
讓你構造一個長度為n的串，逆序數恰好為m且字典序比某字符串string大，請構造字典序最小的這樣的串。
算法分析：
在某個位置i，假設之前的位置都已經構造好了，那么我們在位置i選擇一個字母，我們就可以計算出后面最壞情況下的逆序數最大為多少。
如果比m大，這個字母就可以選。我們每次都選擇最小的這樣的字母就可以了。
1 #include<iostream>
2 #include<
string>
3 using namespace std;
4 int vis[300]={0};
5 int cal(
int n) {
return n * (n-1) /2;}
6 int ret(
string ch){
7 int ans = 0;
8 for(
int i=1;i<ch.size();i++)
9 for(
int j=0;j<i;j++)
10 if(ch[j] > ch[i]) ans ++;
11 return ans;
12 }
13 bool can(
string pre,
char now,
int len,
int res){
14 cout<<pre<<" "<<now;
15 pre.push_back(now);
16 int mx = cal(len - pre.size()) + ret(pre);
17 for(
char i = 'a'; i<'a'+len; i++)
18 if(!vis[i] && i!=now){
19 for(
int j = 0; j<pre.size();j++)
20 mx += (pre[j] > i);
21 }
22 cout<<mx<<endl;
23 return mx >= res;
24 }
25 class StrIIRec {
26 public :
string recovstr(
int n,
int mnv,
string str){
27 string ans = "";
28 bool flag = 1;
29 for(
int i=0;i<n;i++){
30 if(i >= str.size()) flag = 0;
31 char j;
32 for(j = 'a'; j<'a'+n; j++)
if(!vis[j]){
33 // cout<<j<<endl;
34 if(flag && j < str[i])
continue;
35 if(can (ans, j, n, mnv)){
36 ans .push_back(j);
37 if(flag && j > str[i]) flag=0;
38 vis[j] = 1;
39 break;
40 }
41 }
42 if(j >= 'a'+n)
return "";
43 }
44 return ans;
45 }
46 };
47 500pt：
你可以在h*l的網格上以(x,0)為起點畫一條非水平的射線，x為任意的小于l的非負整數。 在這個射線上每次至少要取K個整數坐標。
問一共可以取得多少個不同的坐標集合(1<=h,l,k<=2000)。
算法分析：
因為這個射線上第一個整數坐標點的橫縱坐標一定是互質的，所以我們先花O(n*n*logn)的時間來枚舉出所有互質的數i,j，相當于枚舉射線的斜率了。
對于每一個斜率，我們要知道他在不同的起點x上會得到多少個整數坐標點f(x)，然后ans加上2*C(f(x),k)就可以了。
組合數的問題我們可以打表搞定，對于起點x我們如果依次枚舉的話會超時。
我們設斜率是-j/i，我們會發現x只在每增加i的時候f(x)才會有可能增加1。
于是搞定了~~復雜度O(n^2*log^2n)
1 #include<iostream>
2 using namespace std;
3 typedef long long ll;
4 const int V= 2005;
5 const int mod = 1000000007;
6 ll C[V][V] = {0};
7 int gcd(int a,int b) {return b == 0 ? a : gcd(b,a%b);}
8 class Spacetsk{
9 public: int countsets(int l,int h,int k){
10 if(k == 1) return (l+1) *(h+1) % mod;
11 C[0][0] = 1;
12 for(int i=1; i<V; i++){
13 C[i][0] = 1;
14 for(int j = 1; j<=i;j++)
15 C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
16 }
17 ll ans = 0;
18 for(int i=0;i<=l;i++) ans = ( ans + C[h+1][k] ) % mod;
19 for(int i = 1; i<=l; i++)
20 for(int j = 1; j<=h; j++)
21 if(gcd(i,j) == 1){
22 ll sum = 0, cnt = 0;
23 for(int x = 0,y = 0; x <=l; x += i, y+= j){
24 if(y <= h) cnt ++;
25 ll mt = min(i, l-x+1);
26 sum = (sum + mt * C[cnt][k] ) % mod;
27 }
28 ans = (ans + sum * 2) % mod;
29 }
30 return ans;
31 }
32 };
posted on 2012-06-08 01:54
西月弦 閱讀(615)
評論(0) 編輯 收藏 引用 所屬分類:
比賽感言