A.Two Rabbits
题意：两只兔子一开始在x、y两点，每次相向跳a、b步，询问是否能在某一时刻相遇，如果能则输出时刻
题解：水题，直接模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll x,y,a,b;
scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
if((y-x)%(a+b)==0)
printf("%lld\n",(y-x)/(a+b));
else
puts("-1");
}
return 0;
}B.Longest Palindrome
题意：给你n个长度为m的字符串，选择其中若干个字符串相连接，问你最长能组成多长的回文串，输出长度和字符串。
题解：发现如果存在一个自身是回文串的则将它放在中间，其余的搜索一下，对称放即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
map<string,int>mp;
vector<int>v;
vector<pair<int,int>>v1;
string str[105];
int vis[105];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
string s;
cin >> s;
str[i]=s;
int flag=1;
for(int j=0;j<m/2;j++)
{
if(s[j]!=s[m-1-j])
{
flag=0;
break;
}
}
if(flag)
v.push_back(i);
string t;
for(int j=m-1;j>=0;j--)
t += s[j];
if(mp[t])
v1.push_back({i,mp[t]});
else
mp[s]=i;
}
string s1,s2;
int cnt = 0;
for(int i=0;i<v1.size();i++)
{
auto it = v1[i];
if(vis[it.first]||vis[it.second])
continue;
cnt += 2;
vis[it.first]=vis[it.second]=1;
s1 = s1 + str[it.first];
s2 = str[it.second] + s2;
}
for(int i=0;i<v.size();i++)
{
if(!vis[v[i]])
{
cnt++;
s1 = s1 + str[v[i]];
break;
}
}
printf("%d\n",m*cnt);
cout << s1<<s2 << endl;
return 0;
}C.Air Conditioner(思维)
题意：一共有n个顾客，一开始餐厅温度为m，第i个顾客在第ti分钟到来，他的满意温度在li~hi，你对餐厅可以有三种操作：1、升温：每分钟升高2；2、保温：温度保持不变；3：降温：每分钟降低2。询问你是否能使所有顾客满意
题解：我们可以维护一个区间，这个区间是你所能操控餐厅温度的范围，每次和当前顾客的满意区间比较，然后更新你能操控温度的范围即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
struct People
{
ll t,l,h;
bool operator<(const People & C)const{
return t < C.t;
}
}p[105];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
ll m;
scanf("%d%lld",&n,&m);
for(int i=0;i<n;i++)
scanf("%lld%lld%lld",&p[i].t,&p[i].l,&p[i].h);
sort(p,p+n);
ll L = m , R = m;
int flag = 1;
ll t = 0;
for(int i=0;i<n;i++)
{
ll cnt = p[i].t - t;
L = L - cnt;
R = R + cnt;
if(R<p[i].l||L>p[i].h)
{
flag=0;
break;
}
L = max(L,p[i].l);
R = min(R,p[i].h);
t = p[i].t;
}
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}D.Shortest and Longest LIS（思维+模拟）
题意：给你n-1个由'<'和'>'组成的序列，表示前后两个数的大小关系，让你构造出长度为n，由1~n中的数组成的最短上升子序列和最长上升子序列。
题解：对于最短上升子序列我们只要前一段趋势都比后一段高即可，对于最长上升子序列我们只要后一段趋势都比前一段高即可。这道题我们画出折线图比较好理解
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
char s[N];
int n, a[N];
void getmax() {
int L = 0, pre = 0;
for(int i = 1; i <= n; i++) {
if(s[i] == '>') continue;
else {
for(int j = i; j > pre; j--) a[j] = ++L;
pre = i;
}
}
for(int i = 1; i <= n; i++) printf("%d ", a[i]);
printf("\n");
}
void getmin() {
int L = n + 1, pre = 0;
for(int i = 1; i <= n; i++) {
if(s[i] == '<') continue;
else {
for(int j = i; j > pre; j--) a[j] = --L;
pre = i;
}
}
for(int i = 1; i <= n; i++) printf("%d ", a[i]);
printf("\n");
}
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d", &n);
scanf(" %s", s + 1);
getmin();
getmax();
}
}E.1-Trees and Queries
题意：给你一棵n个节点的树，q组询问，每组询问给你x、y、a、b、k，表示在x和y节点之间连一条边，问你在a和b节点之间能否扎到一条长度为k的路径，其中边和点可以重复走。
题解：我们只要找一条路径，这条路径的长度小于等于k，并且奇数性与k相同即可，因为我们可以一直在两点之间来回使长度增加到k。而最短路径只会有3种情况：1、a→b；2、a→x→y→b；3、a→y→x→b。长度用lca算即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int n, q, f[18][maxn], h[maxn];
vector<int> G[maxn];
void dfs(int x)
{
for (int i = 0; i < G[x].size(); i++)
{
int v = G[x][i];
if (v == f[0][x])
continue;
f[0][v] = x;
h[v] = h[x] + 1;
dfs(v);
}
}
void lca_init()
{
dfs(1);
for (int i = 1; i <= 17; i++)
{
for (int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][f[i - 1][j]];
}
}
}
int lca(int x, int y)
{
if (h[x] < h[y])
swap(x, y);
for (int i = 17; i >= 0; i--)
{
if ((h[x] - h[y]) >> i)
{
x = f[i][x];
}
}
if (x == y)
return x;
for (int i = 17; i >= 0; i--)
{
if (f[i][x] != f[i][y])
{
x = f[i][x];
y = f[i][y];
}
}
return f[0][x];
}
int dis(int x, int y)
{
return h[x] + h[y] - h[lca(x, y)] * 2;
}
bool check(int x, int y)
{
return y >= x && x % 2 == y % 2;
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
lca_init();
cin >> q;
for (int i = 0; i < q; i++)
{
int x, y, a, b, k;
cin >> x >> y >> a >> b >> k;
if (check(dis(a, b), k) ||
check(dis(a, x) + dis(y, b) + 1, k) ||
check(dis(a, y) + dis(x, b) + 1, k))
puts("YES");
else
puts("NO");
}
}
F.Animal Observation（dp+线段树）
题意：一个人去森林摄像，一共去m天，他有两台摄像机，奇数天会把一台摄像机放在一个区域，偶数天会把另一台摄像机放在一个区域，每台摄像机会放置在同一个区域连续两天，每台摄像机能拍摄k个区域，每个区域都有动物。问你最多能拍摄多少只动物
题解：dp[i][j]表示第i天把相机放在第j个区域最大能拍摄动物的数量，因为相机会连续拍摄两天，所以每个区域的影响应该包括两天，而第二天的dp[i+1][j]当天的贡献因为dp[i][j]已经算过了，所以我们在算第i+1天的时候要把dp[i][j]的第i+1的贡献减去，可以用滑动窗口来实现，因为拍摄范围是k，所以i~i+k-1都需要减去，所以我们可以用线段树来维护。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e4+6;
int n,m,k;
int ani[55][maxn],dp[55][maxn],sum[55][maxn];
struct node{
int l,r;
int mx;
int tag;
}tr[maxn*4];
void build(int k,int s,int t)
{
tr[k].l=s;tr[k].r=t;
if(s==t){tr[k].mx=0;return;}
int mid=(s+t)>>1;
build(k<<1,s,mid);
build(k<<1|1,mid+1,t);
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
void pushdown(int k)
{
tr[k<<1].tag+=tr[k].tag;
tr[k<<1|1].tag+=tr[k].tag;
tr[k<<1].mx+=tr[k].tag;
tr[k<<1|1].mx+=tr[k].tag;
tr[k].tag=0;
}
void update(int k,int a,int b,int x)
{
int l=tr[k].l,r=tr[k].r;
if(a==l&&r==b)
{
tr[k].tag+=x;
tr[k].mx+=x;
return;
}
if(tr[k].tag)pushdown(k);
int mid=(l+r)>>1;
if(b<=mid)update(k<<1,a,b,x);
else if(a>mid)update(k<<1|1,a,b,x);
else
{
update(k<<1,a,mid,x);
update(k<<1|1,mid+1,b,x);
}
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
int ask(int k,int a,int b)
{
int l=tr[k].l,r=tr[k].r;
if(a==l&&b==r){return tr[k].mx;}
if(tr[k].tag)pushdown(k);
int mid=(l+r)>>1;
if(b<=mid)return ask(k<<1,a,b);
else if(a>mid)return ask(k<<1|1,a,b);
else return max(ask(k<<1,a,mid),ask(k<<1|1,mid+1,b));
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ani[i][j];
sum[i][j]=sum[i][j-1]+ani[i][j];
}
for(int i=1;i<=m-k+1;i++)
dp[1][i]=(sum[1][i+k-1]-sum[1][i-1])+(sum[2][i+k-1]-sum[2][i-1]);
for(int i=2;i<=n;i++)
{
memset(tr,0,sizeof(tr));
build(1,1,2*m);
for(int j=1;j<=m;j++)
update(1,j,j,dp[i-1][j]);
for(int j=1;j<=k;j++)
update(1,1,j,-ani[i][j]);
for(int j=1;j<=m-k+1;j++)
{
dp[i][j]=max(dp[i][j],ask(1,1,m)+sum[i][j+k-1]-sum[i][j-1]+sum[i+1][j+k-1]-sum[i+1][j-1]);
update(1,max(1,j-k+1),j,ani[i][j]);
update(1,j+1,j+k,-ani[i][j+k]);
}
}
int ans = -1;
for(int i=1;i<=m;i++)
ans=max(ans,dp[n][i]);
cout<<ans<<endl;
}
京公网安备 11010502036488号