A. Drill Wood to Make Fire
问题的题意是：给定木材着火的临界值N，燧人氏的强度S和速度V，你能确定燧人氏是否能钻木取火？
即满足条件为：s*v>=n。满足输出1，否则输出0.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,n,s,v;
cin>>t;
while(t--)
{
cin>>n>>s>>v;
if(s*v>=n) cout<<1<<'\n';
else cout<<0<<'\n';
}
return 0;
}
B. Wonderful Array
思路：因为答案是求(bi mod m<=bi+1 mod m)的个数，所以在求之前对b数组mod m对答案是没有影响。
得到新的数组b后直接去统计bi mod m<=bi+1 mod m的个数1e9的时间复杂度肯定过不了，所以可以找不满足的个数,
即bi mod m>bi+1 mod m的个数。最后用b数组总个数n减去这个长度就是满足的个数。在数组中要满足bi mod m<=bi+1 mod m
的条件为bi+ai>=m，所以只需要计算在累加的过程中产生了多少次取模即可。即答案ans=n-bn/m;
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll a[N],b,n,m,x,k,sum=0;
cin>>k;
for(int i=1;i<=k;i++){
cin>>a[i];
}
cin>>n>>m>>x;
b=x%m;//b的第一项为x
for(int i=1;i<=k;i++){
a[i]%=m;
sum+=a[i];//计算k数组中数的总和
}
b+=(n/k)*sum;//计算长度为n的数组b需要累加多少轮k数组和
ll res=n%k;
for(int i=1;i<=res;i++){//将不足k个数的数加上
b+=a[i];
}
cout<<n-b/m;
return 0;
}
C. Battle
题意：A和B玩取石子游戏，第一行输入n，p，第二行输入n个数，有n堆石子，每个数代表一堆石子的个数。接下来两个人轮流进行一次操作。
每次操作可以任选一堆石子取走p的非负整数次方个石子，不能不取。当有一方不能进行操作时，则输掉比赛。如果先手的能赢则输出GOOD，
否则输出BAD。
思路：多组博弈时可以先用sg函数异或合并大表找到规律。可以发现当p为奇数时，sg(x)=x mod 2;
当p为偶数时，如果x mod (p+1)=p，则sg(x)==2，否则sg(x)=(x mod p+1)%2;
将所有sg值异或起来后,如果答案不为零则先手必胜，否则先手必败。
#include <bits/stdc++.h>
using namespace std;
const int N = 110,M=3e5+10;
typedef long long ll;
ll x,p,n,res;
ll sg1(ll x)//x为奇数的情况
{
return x%2;
}
ll sg2(ll x)//x为偶数的情况
{
if(x==p) return 2;
if(x%2==0) return 0;
else return 1;
}
int main()
{
res=0;
cin>>n>>p;
for(ll i=0;i<n;i++){
cin>>x;
if(p&1)
{
res^=sg1(x);
}
else
{
x%=(p+1);
res^=sg2(x);
}
}
if(res) cout<<"GOOD"<<'\n';
else cout<<"BAD"<<'\n';
return 0;
}
J. Function
题意：给定一个系数为1的二次函数，第i个方程为y=(x-i)2+bi。给出一个正整数n和n个bi。接下来给出一个m代表有m此操作。操作有两种，
如果输入形式为“1 x“则进行第一种操作，输出y=(x-i)2+bi的最小值。如果输入形式为”0 a b“则进行第二种操作，添加一个方程为y=(x-a)2+b。
思路：在二次项中i=x时，y=bi。所以只需要在x-sqrt(bi)到x+sqrt(bi)范围内枚举取最小值即可。范围外的值一定会大于bi。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m,te[N];
cin>>n;
for(int i=1;i<=n;i++){
cin>>te[i];
}
cin>>m;
while (m -- )
{
int a,b,x,op;
cin>>op;
if(op==1)
{
cin>>x;
int ans=te[x];
double p=sqrt(te[x]);
int l=max(1,x-(int)ceil(p));
int r=min(n,x+(int)ceil(p));
for(int i=l;i<=r;i++){
ans=min(ans,(x-i)*(x-i)+te[i]);
}
cout<<ans<<'\n';
}
else if(op==0)
{
cin>>a>>b;
if(te[a]>b) te[a]=b;
}
}
return 0;
}
K. Split
题意：给定一个n，然后输入a1，a2，...，an，ai>=ai+1。有m次操作，操作1：输入”1 k”，将a数组分为k段，输出每段最大值和最小值差的和最小。
操作2：输入“0 x”，将ax变成ax-1+ax+1-ax。
思路：操作2将ax变成ax-1+ax+1-ax只改变了数值，并没有改变数列中的差值。而1操作可以看成将一段数插入k-1个板子，每插入一个板子，当前位置的差值就会消失，
所有可以将相邻的两个数的差值统计出来，除去k-1个最大的差值即可得到最小的差值和。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,a[N],ex[N],m,arr[N];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i!=1)
{
ex[i]=a[i-1]-a[i];
}
}
sort(ex+1,ex+n+1);
for(int i=1;i<=n;i++){
arr[i]=arr[i-1]+ex[i];
}
cin>>m;
while(m--)
{
int op,x;
cin>>op>>x;
if(op==1)
{
cout<<arr[n-x+1]<<'\n';
}
}
return 0;
}
L.Zhang Fei Threading Needles - Thick with Fine
题意：输出一个n，输出n-1.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
cout<<n-1;
return 0;
}