比賽鏈接
鏈接
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 <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
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 <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 1e5+10;
int n , m;
int a[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin >> 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 <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
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 <= n;i ++)
cin >> 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500530.html
標籤：其他