比赛链接
A. Three Doors
题目链接
题目描述
输入
输出
样例
输入
4
3
0 1 2
1
0 3 2
2
3 1 0
2
1 3 0
输出
YES
NO
YES
NO
题目大意
面前有三个门，编号分别为1，2，3。
再给你一把编号为x的钥匙，打开每扇门后，可以有一把编号为 a[i]的钥匙，判断所给的x是否能把三扇门都打开。
思路
按照题意进行模拟，并且用 a[]存放钥匙编号, st[]用来判断门是否打开
代码
#include
#include
#include
#include
#include
using namespace std;
void solve()
{
int x ;
cin >> x;
int a[4];
cin >> a[1] >> a[2] >> a[3];
bool st[4];
memset(st,false,sizeof st);
while(x != 0)
{
st[x] = true;
x = a[x];
}
if(st[1] && st[2] && st[3])
puts("YES");
else
puts("NO");
}
int main()
{
int T;
cin >> T;
while(T --)
solve();
return 0;
}
B. Also Try Minecraft
题目链接
题目描述
输入
输出
样例
输入
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2
输出
2
10
0
7
3
1
题目大意
给你n个数，m组x,y。判断从 a[x]到 a[y]两个数之间的减少量是多少。
比如样例中 1 7，判断从 a[1]到 a[7]中的减少的数是多少
[10 - 8]+[9 - 6]+[12 - 7] = 2 + 3 + 5 = 10
思路
按照题意进行模拟会造成超时，所以可以采用前缀和。
需要对m组数据进行分类，因为有的是从左到右，有的是从右到左。
left[i] = left[i-1] + max(0ll , a[i] - a[i+1])
right[i] = right[i-1] + max(0ll , a[i+1] - a[i])
其中 0ll表示 long long状态下的 0
模拟代码（会TLE）
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
int n , m;
int a[N];
int main()
{
cin >> n >> m;
for(int i = 1;i > a[i];
while(m --)
{
int x , y;
cin >> x >> y;
int cnt = 0;
if(x < y)//从左到右
{
for(int i = x;i < y;i ++)
if(a[i] > a[i+1])
cnt += a[i] - a[i+1];
}
else if(x > y)//从右往左
{
for(int i = x;i > y;i --)
if(a[i] > a[i-1])
cnt += a[i] - a[i-1];
}
cout << cnt << endl;
}
return 0;
}
前缀和代码
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll a[N];
ll le[N] , ri[N];
ll n , m , x , y;
int main()
{
cin >> n >> m;
for(int i = 1;i > a[i];
memset(le,0ll,sizeof(le));
memset(ri,0ll,sizeof(ri));
for(int i = 1;i < n;i ++)
{
le[i] = le[i-1] + max(0ll , a[i] - a[i+1]);
ri[i] = ri[i-1] + max(0ll , a[i+1] - a[i]);
}
while(m --)
{
cin >> x >> y;
if(x < y)
cout << le[y-1] - le[x-1] << endl;
else
cout << ri[x-1] - ri[y-1] << endl;
}
return 0;
}
Original: https://www.cnblogs.com/heystar/p/16529238.html
Author: HeyStar
Title: 【CodeForces】Educational Codeforces Round 132 (Rated for Div. 2)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587921/
转载文章受原作者版权保护。转载请注明原作者出处！