吐槽：
1. 大家可能會疑惑544的總結(jié)呢。。。 因?yàn)?44掛0了，就不寫總結(jié)了額 - -
2. 周末參加?xùn)|北賽，祝自己好運(yùn)
3. 漲了166pt真是耗人品
4. 下周數(shù)電實(shí)驗(yàn)答辯(20頁的報(bào)告我擦)+電子技術(shù)考試，真是煩?。。。?！
5. 最后一個(gè)賽季，fighting!!! 要么出線要么滾蛋...
其實(shí)我在房間實(shí)在太弱了 - -
275pt:
讓你構(gòu)造一個(gè)長度為n的串，逆序數(shù)恰好為m且字典序比某字符串string大，請構(gòu)造字典序最小的這樣的串。
算法分析：
在某個(gè)位置i，假設(shè)之前的位置都已經(jīng)構(gòu)造好了，那么我們在位置i選擇一個(gè)字母，我們就可以計(jì)算出后面最壞情況下的逆序數(shù)最大為多少。
如果比m大，這個(gè)字母就可以選。我們每次都選擇最小的這樣的字母就可以了。
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的網(wǎng)格上以(x,0)為起點(diǎn)畫一條非水平的射線，x為任意的小于l的非負(fù)整數(shù)。 在這個(gè)射線上每次至少要取K個(gè)整數(shù)坐標(biāo)。
問一共可以取得多少個(gè)不同的坐標(biāo)集合(1<=h,l,k<=2000)。
算法分析：
因?yàn)檫@個(gè)射線上第一個(gè)整數(shù)坐標(biāo)點(diǎn)的橫縱坐標(biāo)一定是互質(zhì)的，所以我們先花O(n*n*logn)的時(shí)間來枚舉出所有互質(zhì)的數(shù)i,j，相當(dāng)于枚舉射線的斜率了。
對于每一個(gè)斜率，我們要知道他在不同的起點(diǎn)x上會得到多少個(gè)整數(shù)坐標(biāo)點(diǎn)f(x)，然后ans加上2*C(f(x),k)就可以了。
組合數(shù)的問題我們可以打表搞定，對于起點(diǎn)x我們?nèi)绻来蚊杜e的話會超時(shí)。
我們設(shè)斜率是-j/i，我們會發(fā)現(xiàn)x只在每增加i的時(shí)候f(x)才會有可能增加1。
于是搞定了~~復(fù)雜度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
西月弦 閱讀(601)
評論(0) 編輯 收藏 引用 所屬分類:
比賽感言