SRM 468
DIV1 250pt
题意：给出字典，按照一定要求进行查找。
解法：模拟题，暴力即可。
tag:water
score: 0....
这是第一次AC的代码：
/*
* Author: plum rain
* score : 0
*/
#line 11 "T9.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef vector<string> VS; map<char, int> mp; class T9
{
public:
string message(vector <string> part, vector <string> dict, vector <string> ke){
int size = SZ (part);
for (int i = ; i < size; ++ i)
for (int j = ; j < SZ(part[i]); ++ j)
mp[part[i][j]] = i+; VS dic; dic.clear();
size = SZ (dict);
for (int i = ; i < size; ++ i){
string s; s.clear();
int n = SZ (dict[i]);
for (int j = ; j < n; ++ j)
s.PB (mp[dict[i][j]] + '');
dic.PB (s);
} for (int i = ; i < size; ++ i)
for (int j = ; j < size--i; ++ j){
bool ok = false;
if (dic[j] < dic[j+]) ok = true;
if (dic[j] == dic[j+] && dict[j] > dict[j+])
ok = true;
if (ok){
swap (dic[j], dic[j+]);
swap (dict[j], dict[j+]);
}
} string ans; ans.clear();
size = SZ (ke);
string s; s.clear();
for (int i = ; i < size; ++ i)
s += ke[i];
size = SZ (s);
string tmp; tmp.clear();
int cnt = ;
for (int i = ; i < size; ++ i){
if (s[i] == '*') cnt += ;
if (s[i] == '#') ++ cnt;
if (s[i] >= '' && s[i] <= '') tmp.PB(s[i]);
if (s[i] == ''){
if (tmp.empty() && !cnt){
ans.PB (' ');
continue;
}
int pos;
for (int j = ; j < SZ (dic); ++ j)
if (dic[j] == tmp){
pos = j;
break;
}
pos = pos + cnt;
ans = ans + dict[pos];
cnt = ; tmp.clear();
ans.PB (' ');
}
}
if (tmp.empty() && !cnt) return ans;
int pos;
for (int i = ; i < SZ (dic); ++ i)
if (dic[i] == tmp){
pos = i;
break;
}
pos = pos + cnt;
ans = ans + dict[pos];
return ans;
}
};
这是后来改进的代码：
/*
* Author: plum rain
* score : 0
*/
#line 11 "T9.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <map> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef vector<string> VS; map<char, int> mp; bool cmp(pair<string, string> a, pair<string, string> b)
{
if (a.first < b.first) return true;
if (a.first == b.first && a.second < b.second) return true;
return false;
} class T9
{
public:
string message(vector <string> part, vector <string> dict, vector <string> ke){
int size = SZ (part);
mp.clear();
for (int i = ; i < size; ++ i)
for (int j = ; j < SZ(part[i]); ++ j)
mp[part[i][j]] = i+; vector<pair<string, string> > D; D.clear();
size = SZ (dict);
for (int i = ; i < size; ++ i){
string s; s.clear();
int n = SZ (dict[i]);
for (int j = ; j < n; ++ j)
s.PB (mp[dict[i][j]] + '');
D.PB (make_pair(s, dict[i]));
}
sort (D.begin(), D.end(), cmp); size = SZ (ke);
string s; s.clear();
for (int i = ; i < size; ++ i)
s += ke[i];
s.PB ('');
size = SZ (s); string tmp; tmp.clear();
string ans; ans.clear();
int cnt = ;
for (int i = ; i < size; ++ i){
if (s[i] == '*') cnt += ;
if (s[i] == '#') ++ cnt;
if (s[i] >= '' && s[i] <= '') tmp.PB(s[i]);
if (s[i] == ''){
if (tmp.empty() && !cnt){
if (i != (size-))
ans.PB (' ');
continue;
}
int pos;
for (int j = ; j < SZ (D); ++ j)
if (D[j].first == tmp){
pos = j;
break;
}
pos = pos + cnt;
ans = ans + D[pos].second;
cnt = ; tmp.clear();
if (i != (size-))
ans.PB (' ');
}
}
return ans;
}
};
SRM 469
DIV1 250pt
题意：给定n * m的网格中，其中有若干点不能被选择，然后从其他点中选出同行且相邻的两点，问有多少种选择方法？(1 <= n,m <= 10^8)
解法：水题
score: 129.09
tag: math, counting
/*
* Author: plum rain
* score: 129.09
*/
#line 10 "TheMoviesLevelOneDivOne.cpp"
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <vector> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef long long int64; struct pos{
int x, y;
}; pos a[]; bool cmp(pos a, pos b)
{
if (a.x < b.x)
return true;
if (a.x == b.x && a.y < b.y)
return true;
return false;
} int64 gao(int64 size, int64 n, int64 m)
{
int i = ;
int64 tmp = a[].x, dif = ;
if (a[].y == ) dif = ;
if (a[].y >= ) dif = ;
while (i < size){
if (tmp == a[i].x){
if (a[i-].y == a[i].y-) ++ dif;
else dif += ;
++ i;
continue;
} if (a[i-].y == m) -- dif;
if (a[i].y == ) ++ dif;
if (a[i].y >= ) dif += ;
tmp = a[i].x;
++ i;
}
if (a[i-].y == m) -- dif; return n * (m-) - dif;
} class TheMoviesLevelOneDivOne
{
public:
long long find(int n, int m, vector <int> row, vector <int> seat){
CLR (a);
int size = SZ (row);
for (int i = ; i < size; ++ i)
a[i].x = row[i], a[i].y = seat[i];
sort (a, a+size, cmp); return (gao(size, n, m));
}
};
DIV1 500pt
题意：一个人看电影，该人有一个scare值，并且没看1min电影scare减1。有很多部恐怖电影，每部电影长度不同(length[i])，且每部都有一个瞬间增加scare(s[i])值的时刻。如果scare值小于0，则这个人就会睡着，不能再看电影。请问他安排一个电影观看顺序，使得他能看尽可能多的电影。如果有多组观看顺序看到的电影数相同，则输出字典序最小的。(电影数量小等于20)
解法：如果这道题不要求输出字典序最小的，而是随便输出一组，那就是一道很简单的贪心题。- -
状压DP。假设有n部电影，用opt来表示所有电影是否排进观影序列(1为该电影未进入观影序列)，用num[opt]表示观影序列为opt时所能看的电影数量的最大值，用scare表示观影序列为opt时看完观影序列上的电影后的scare值。则状态转移方程为：
if (opt & (1<<i) && scare >= s[i] && scare >= length[i] - 47) num[opt] = 1 + num[opt - (1<<i)]，for i = 0 to n-1。注意还要记录路径。
score: 0
tag:DP, good
/*
* Author: plum rain
* score : 0
*/
#line 10 "TheMoviesLevelTwoDivOne.cpp"
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <vector> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl typedef vector<int> VI; const int N = ;
int n;
vector<pair<int, int> > a;
int num[<<N], fir[<<N]; VI DP()
{
CLR (num); CLR (fir);
for (int opt = ; opt < (<<n); ++ opt){
int flag, tmp = -;
int sca = ;
for (int i = ; i < n; ++ i)
if (!(opt & (<<i))) sca += - a[i].first; for (int i = ; i < n; ++ i) if (opt & (<<i)){
int x = ;
if (sca >= a[i].second && sca >= (a[i].first - ))
x = + num[opt-(<<i)];
if (x > tmp)
tmp = x, flag = i;
} num[opt] = tmp;
fir[opt] = flag;
} int opt = (<<n) - ;
VI ret; ret.clear();
while (opt > ){
ret.PB (fir[opt]);
opt -= (<<fir[opt]);
}
return ret;
} class TheMoviesLevelTwoDivOne
{
public:
vector <int> find(vector <int> ls, vector <int> sc){
n = SZ (ls);
a.clear();
for (int i = ; i < n; ++ i)
a.PB(make_pair(ls[i], sc[i])); return (DP());
}
};