A
考虑都是格点 , 枚举所有y+-0.5就行了.
trick是避免正好在y上的点重复统计.
class PiecewiseLinearFunction {
public:
int maximumSolutions(vector <int>);
};
int n;
int cross(vector<int> Y,double y) {
int res=;
double l,r;
l = (double)Y[];
r = (double)Y[];
for (int i= ; i<n ; i++ ) {
if (y>l && r>l && y<r) res++;
else if (y<l && r<l && y>r) res++;
l = r;
if (i+<n) r = Y[i+];
}
for (int i= ; i<n ; i++ ) if (fabs(Y[i]-y)<1e-) res++;
return res;
}
int solv(vector<int> Y) {
for (int i= ; i<n ; i++ ) if (Y[i]==Y[i-]) return -;
if (Y.size()==) return ;
int res = ;
for (int i= ; i<n ; i++ ) {
int tmp = cross(Y,Y[i]);
res = max(res,tmp);
tmp = cross(Y,Y[i]+0.5);
res = max(res,tmp);
tmp = cross(Y,Y[i]-0.5);
res = max(res,tmp);
printf("y:%d tmp:%d\n",Y[i],tmp);
}
return res;
}
int PiecewiseLinearFunction::maximumSolutions(vector <int> Y) {
n = Y.size();
int ans = solv(Y);
return ans;
}
B
差分约束模型,每一条历史记录可以转化成一条约束,然后建边求最短路.
a->b的最短路和b->a的最短路可以确定一个区间[l,r] 如果l>r则该区间不存在,
判断是否可能时 , 检查线段是否有交点.
using namespace std;
#define maxn 100
#define INF 1000000000
vector<int> his[maxn];
int n,f[maxn][maxn];
class History {
public:
string verifyClaims(vector <string>, vector <string>, vector <string>);
}; void addedge(int a,int ida,int b,int idb) {
int sa = his[a][ida] , ta = his[a][ida+]-;
int sb = his[b][idb] , tb = his[b][idb+]-;
int b_a = ta-sb;
int a_b = tb-sa;
f[b][a] = min(f[b][a],b_a);
f[a][b] = min(f[a][b],a_b);
} void floyd() {
for (int k= ; k<n ; k++ )
for (int i= ; i<n ; i++ )
for (int j= ; j<n ; j++ )
f[i][j] = min(f[i][j] , f[i][k]+f[k][j]);
} void pretreat(vector<string> dyn , vector<string> war) {
n = dyn.size();
for (int i= ; i<n ; i++ ) {
stringstream ss(dyn[i]);
int num;
while (ss>>num) his[i].push_back(num);
} for (int i= ; i<n ; i++ )
for (int j= ; j<n ; j++ ) f[i][j] = INF; string s="";
for (int i= ; i<(int)war.size() ; i++ ) s += war[i];
stringstream ss(s);
string t;
while (ss>>t) {
char a,b;
int ida,idb;
sscanf(t.c_str(),"%c%d-%c%d",&a,&ida,&b,&idb);
addedge(a-'A',ida,b-'A',idb);
}
floyd();
} char check(int a,int ida,int b,int idb) {
int sa = his[a][ida] , ta = his[a][ida+]-;
int sb = his[b][idb] , tb = his[b][idb+]-;
int r = ta-sb;
int l = sa-tb;
int R = f[b][a];
int L = -f[a][b];
if (l>R || r<L) return 'N';
return 'Y';
} string History::verifyClaims(vector <string> dyn, vector <string> war, vector <string> query) {
pretreat(dyn,war);
string res="";
for (int i= ; i<(int)query.size() ; i++ ) {
string t = query[i];
char a,b;
int ida,idb;
sscanf(t.c_str(), "%c%d-%c%d",&a,&ida,&b,&idb);
res += check(a-'A',ida,b-'A',idb);
}
return res;
}
C
首先找出light string的性质:
1. 字符集 = min(26,长度);
2. 相同字母连续出现;
然后发现可以用L,R来表示 从所有串看来,某字母的使用区间 , 第一次使用是L,
最后一次使用是R , 然后就是找到一些约束条件和相关变量,枚举变量dp ,利用约束条件优化复杂度...
int f[maxn][][] , len[maxn] , n;
int dfs(int i,int a,int o,vector<int> L) {
int & res = f[i][a][o];
if (res == -){
res = INF;
if (i==n) {
if (o==) {
res = ;
}
} else {
int s = i->=?len[i-]:;
int m = min(L[i],);
for (int c= ; c<=m && c<=o ; c++ ) {
for (int p= ; c+p<=m && p<=a ; p++ ) {
for (int u= ; p+u+c<=m && u+c<=o ; u++ ) {
int k = m-(c+u+p);
if (p+k>a) continue;
int w = dfs(i+,a-k-p,o-c+p,L);
if (u > ) {
w += s*c + (c-)*c/;
w -= (s+L[i]-)*p - (p-)*p/;
} else {
w += s*c + (c-)*c/;
w -= (s+L[i]-)*p - (p-)*p/;
w += L[i]-(c+p+k);
}
res = min(res,w);
}
}
}
}
}
return f[i][a][o] = res;
}
int StringWeight::getMinimum(vector <int> L) {
n = L.size();
memset(f, -, sizeof(f));
for (int i= ; i<n ; i++ ) len[i] = i==?L[i]:len[i-]+L[i];
int ans = dfs(,,,L);
return ans;
}