A题,水题略过。
B题,也水,但是想复杂了。只要运动超出[0,20000]的范围就算不可能了。
C题,我自己的方法是解不等式,然后取最大的答案即可。代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
const int N = + ;
const int inf = 2e9; int main()
{
int L = -inf, R = -inf;
int n; cin >> n;
//int add = 0;
int pre = ;
for(int i=;i<=n;i++)
{
int change, d;
scanf("%d%d",&change, &d);
//add += change;
if(d == )
{
if(L == -inf) L = - pre;
else L = max(L, - pre);
}
else
{
if(R == -inf) R = - pre;
else R = min(R, - pre);
}
pre += change;
}
if(L != -inf && R != -inf && L > R) puts("Impossible");
else if(L != -inf && R == -inf) puts("Infinity");
else printf("%d\n",R + pre);
return ;
}
C
D题是记忆化搜索,补题的时候没做出来。。代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
using namespace std;
const int N = + ;
const int inf = 2e9;
typedef pair<int,int> pii; int dirx[] = {,,,,-,-,-,};
int diry[] = {,,-,-,-,,,};
int vis[][][N][N];
int t[], n;
int mp[N][N]; void dfs(int pos, int dir, int x, int y)
{
if(pos > n || vis[pos][dir][x][y]) return ;
vis[pos][dir][x][y] = ;
for(int i=;i<t[pos];i++) mp[x+dirx[dir]*i][y+diry[dir]*i] = ;
x += dirx[dir] * (t[pos] - );
y += diry[dir] * (t[pos] - );
dfs(pos+, (dir+)%, x+dirx[(dir+)%], y+diry[(dir+)%]);
dfs(pos+, (dir+)%, x+dirx[(dir+)%], y+diry[(dir+)%]);
} int main()
{
cin >> n;
for(int i=;i<=n;i++) scanf("%d",t+i);
dfs(,,N/,N/);
int ans = ;
for(int i=;i<N;i++)
{
for(int j=;j<N;j++) ans += mp[i][j];
}
cout << ans << endl;
return ;
}
D
E题,好题。用0~4分别表示拥有2017的前若干个字母的情况,x[i][j]表示从i状态转移到j状态需要删除几个字符,然后进行转移。并且用线段树进行维护答案。具体见代码:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#define ls (o<<1)
#define rs (o<<1|1)
#define t_mid (l+r>>1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
const int N = + ;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pii; int n,q;
char s[N];
struct node
{
int x[][];
node operator + (const node A) const
{
node ans;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
ans.x[i][j] = inf;
for(int k=;k<;k++) ans.x[i][j] = min(ans.x[i][j], x[i][k] + A.x[k][j]);
}
}
return ans;
}
}p[N<<]; void build(int o,int l,int r)
{
if(l == r)
{
for(int i=;i<;i++) for(int j=;j<;j++) p[o].x[i][j] = i==j ? : inf;
if(s[l] == '')
{
p[o].x[][] = ;
p[o].x[][] = ;
}
else if(s[l] == '')
{
p[o].x[][] = ;
p[o].x[][] = ;
}
else if(s[l] == '')
{
p[o].x[][] = ;
p[o].x[][] = ;
}
else if(s[l] == '')
{
p[o].x[][] = ;
p[o].x[][] = ;
}
else if(s[l] == '')
{
p[o].x[][] = ;
p[o].x[][] = ; // 已经有2017,现在多出6,要删掉6
}
return ;
}
build(lson);
build(rson);
// up(o)
p[o] = p[ls] + p[rs];
} node query(int o,int l,int r,int ql,int qr)
{
if(l == ql && r == qr) return p[o];
if(qr <= t_mid) return query(lson,ql,qr);
else if(ql > t_mid) return query(rson,ql,qr);
else return query(lson,ql,t_mid) + query(rson,t_mid+,qr);
} int main()
{
cin >> n >> q;
scanf("%s",s+);
build(,,n);
while(q--)
{
int l, r;
scanf("%d%d",&l, &r);
int ans = query(,,n,l,r).x[][];
printf("%d\n",ans == inf ? - : ans);
}
return ;
}
E