吐槽：
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
西月弦 阅读(574)
评论(0) 编辑 收藏 引用 所属分类:
比赛感言