Codeforces Round #700 (Div. 2)
B-The Great Hero
按总收到伤害排序是不行的(数据:1 1 7 2 2 3 3 1)。简单分析一下,你总是要打死n-1只怪,剩下一只怪你攻击x次杀死他,他只攻击你x-1次。那么就去找这个怪,直接枚举每一只,看看其他怪的伤害总和加上这一只只攻击x-1次后剩余的生命值是否大于0。
C-Searching Local Minimum
噔 噔 噔,心肺停止。 wa5了4发才找到这个问题
每次二分mid与mid+1的两个值,如果a[mid]r时,遍历一遍序列找那个值即可(肯定能找到,nextpermutation打个表画折线图)
代码:
#include
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;
vectora(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 << "! "<> 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给了第二组)
只需要把这种处理掉就行了。(为什么没做出来:造了hack数据,当时贪心先拿了1,然后再去拿2,模拟中间决策写不来,然后就炸了(wa4))
代码:
#include
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;
vectora(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;
}