B-The Great Hero
按总收到伤害排序是不行的,简单分析一下,你总是要打死n-1只怪,剩下一只怪你攻击x次杀死他,他只攻击你x-1次。那么就去找这个怪,直接枚举每一只,看看其
他怪的伤害综合加上这一只只攻击x-1次后剩余的生命值是否大于0。
C-Searching Local Minimum
wa5了4发才找到这个sb问题
每次二分mid与mid+1的两个值,如果a[mid]<a[mid+1],则r=mid-1,否则l=mid+2,最终l>r时,遍历一遍序列找那个值即可(肯定能找到,nextpermutation打个表画折线图)
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const ll inf = 1e8 + 7;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
vector<int>a(n + 2, 0);
if (n == 1)
{
cout << "! 1" << endl;
return 0;
}
cout << "? 1" << endl;
cout.flush();
cin >> a[1];
cout << "? 2" << endl;
cout.flush();
cin >> a[2];
cout << "? " << n - 1 << endl;
cout.flush();
cin >> a[n - 1];
cout << "? " << n << endl;
cout.flush();
cin >> a[n];
if (a[2] > a[1])
{
cout << "! 1" << endl;
return 0;
}
if(a[n] < a[n - 1])
{
cout << "! "<<n<<endl;
return 0;
}
int l = 3, r = n - 2;
while (l <= r)
{
int mid = l + r >> 1;
if (!a[mid])
{
cout << "? " << mid << endl;
cout.flush();
cin >> a[mid];
}
if (!a[mid + 1])
{
cout << "? " << mid + 1 << endl;
cout.flush();
cin >> a[mid + 1];
}
cout.flush();
if (a[mid] < a[mid + 1])
r = mid - 1;
else
l = mid + 2;
}
cout.flush();
for (int i = 2; i < n; i++)
if (a[i] && a[i - 1] && a[i + 1] && a[i] < a[i - 1] && a[i] < a[i + 1])
{
cout <<"! "<< i << endl;
break;
}
return 0;
}
D1-Painting the Array I
错误思路:先拿一组,剩下的全部给第二组,这样会wa6。。。
hack:11332133 错误做法:第一组:13213 第二组13 答案: 第一组:1323 第二组:1313(把1给了第二组)
只需要把这种处理掉就行了
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;
int main()
{
fastio;
int n;
cin >> n;
vector<int>a(n + 1);
int ans = 0, last1 = -1, last2 = -1;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)
{
int x = a[i];
if (x != last1 && x != last2)
{
ans++;
if (i < n && a[i + 1] == last2)last2 = x;
else
last1 = x;
}
else if (x != last1 && x == last2)
{
ans++;
last1 = x;
}
else if (x == last1 && x != last2)
{
ans++;
last2 = x;
}
}
cout << ans;
return 0;
}