比赛链接
趁最近没啥比赛，所以打了之前的一场div3，结果自闭。。。c题爆炸，后面也没时间写，所以只做出了三道题，不过之后还是把剩下几道题自己做出了几道，除了f。。。因为昨天的div2也没打，所以去补那一场了，f暂时没时间补，以后再说吧
不过div3真是难啊，除了第一题，难度都不低，但是也不高，div2就是难度升高贼快。。。。
A. Water Buying
其实挺水的。。。就比较打一升水的成本就行了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e5+3;
const double Pi=acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
int q;
cin>>q;
while(q--)
{
int a,b;
ll n;
cin>>n>>a>>b;
double a1=(double)a;
double b1=(double)b/2;
if(a1<=b1){
cout<<(ll)a*n<<endl;;
}
else {
if(n%2==0){
cout<<(ll)(n/2)*(ll)b<<endl;
}
else {
cout<<(ll)(n/2)*(ll)b+(ll)a<<endl;
}
}
}
}
B. Tanya and Candies
如果一个糖被去掉的话，对于这个糖后面所有的糖来说，之前是奇数的糖会变成偶数，之前是偶数的糖会变成奇数，所以，先求出原本的奇数和与偶数和，再从后往前找，不断更新后面的奇数和与偶数和，通过这四个值就可以计算出，去掉当前这个糖后的奇数和与偶数和，再进行比较就行了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e5+3;
const double Pi=acos(-1.0);
int a[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
ll tot1=0,tot2=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i%2==1)tot1+=a[i];
else tot2+=a[i];
}
ll tot3=0,tot4=0;
int ans=0;
for(int i=n;i>=1;i--)
{
if(i%2==1){
tot3+=a[i];
if(tot1-tot3+tot4==tot2-tot4+tot3-a[i])ans++;
}
else {
tot4+=a[i];
if(tot2-tot4+tot3==tot1-tot3+tot4-a[i])ans++;
}
}
cout<<ans<<endl;
}
C. Palindromic Matrix
。。。坑爹题啊，wa了九次
其实不难，计算数字出现过的次数就行了，n是偶数时好整，就是n要是奇数。。。。哎
直接上代码吧，这个题难度就在代码上。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e5+3;
const double Pi=acos(-1.0);
int s[25*25];
int a[1005];
int mat[25][25];
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n*n;i++)
{
cin>>s[i];
a[s[i]]++;
}
int h2=0,h4=0;
int emmm;
for(int i=1;i<=1000;i++)
{
h4+=a[i]/4;
h2+=a[i]/2;
if(a[i]%2==1)emmm=i;
}
int i=1,j=1;
if(n%2==0&&h4==(n*n)/4){
cout<<"YES"<<endl;
for(int k=1;k<=n*n;k++)
{
if(a[s[k]]){
mat[i][j]=s[k];
mat[n-i+1][j]=s[k];
mat[i][n-j+1]=s[k];
mat[n-i+1][n-j+1]=s[k];
a[s[k]]-=4;
j++;
if(j==(n/2)+1){
i++;j=1;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cout<<mat[i][j]<<((j==n)?'\n':' ');
}
}
else if(n%2==1&&h4>=(n-1)*(n-1)/4&&h2>=(n-1)*(n-1)/2+n-1){
cout<<"YES"<<endl;
mat[n/2+1][n/2+1]=emmm;
a[emmm]--;
int f1=1,f2=0;
for(int k=1;k<=n*n;k++)
{
if(a[s[k]]>=4){
mat[i][j]=s[k];
mat[n-i+1][j]=s[k];
mat[i][n-j+1]=s[k];
mat[n-i+1][n-j+1]=s[k];
a[s[k]]-=4;
j++;
if(j==(n/2)+1){
i++;j=1;
}
if(i==(n/2)+1)break;
}
}
for(int k=1;k<=n*n;k++){
if(a[s[k]]>=2){
if(f2){
mat[f1][n/2+1]=s[k];
mat[n-f1+1][n/2+1]=s[k];
}
else {
mat[n/2+1][f1]=s[k];
mat[n/2+1][n-f1+1]=s[k];
}
a[s[k]]-=2;
f1++;
if(f1==n/2+1&&f2==0){
f1=1;f2=1;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cout<<mat[i][j]<<((j==n)?'\n':' ');
}
}
else cout<<"NO"<<endl;
}
D. Coffee and Coursework (Hard Version)
又是两个版本的题，还是只看难的这个
这个题是后来做出来的，想了半天才想到二分，正好tags里也有二分，所以多想了一会，竟然做出来了，呜呜呜，不容易啊，终于能独立做出二分来了
这个题直接算是很难的，但是如果规定了天数，计算能不能写完却很简单，直接计算最大的页数就行了，而且天数越多，写的最大页数一定越多，所以可以直接二分答案
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e5+3;
const double Pi=acos(-1.0);
ll a[N],h[N];
ll m;
int n;
bool check(int x){
int h=n/x;
int q=n-h*x;
int k=1;
ll sum=0;
for(int i=1;i<=q;i++)
{
sum+=max(a[k]-h,(ll)0);
k++;
}
h--;
for(int i=1;i<=n-q;i++)
{
sum+=max(a[k]-h,(ll)0);
if(i%x==0)h--;
k++;
}
if(sum>=m)return true;
else return false;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
ll tot=0;
for(int i=1;i<=n;i++){
cin>>a[i];
tot+=a[i];
}
sort(a+1,a+n+1);
if(tot<m){
cout<<-1<<endl;
return 0;
}
int l=1,r=n,mid;
while(l<r){
mid=((l+r)>>1);
if(check(mid)){
r=mid;
}
else l=mid+1;
}
cout<<l<<endl;
}
E. Yet Another Ball Problem
水得一匹得题。。。随便一构造就过了我去，就是中间爆了次long long比较尴尬。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e5+3;
const double Pi=acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
ll m=(ll)k*(k-1);
if(m<(ll)n){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
int h=1;
int hh=1;
for(int i=1;i<=n;i++)
{
cout<<h<<' '<<((h+hh>k)?(h+hh)%k:h+hh)<<endl;
h++;
if(h>k){h=1;hh++;}
}
}
F. Tree Cutting (Hard Version)
又是两个版本的题，我就不做了有时间再做。。