Codeforces Round 883 (Div. 3)(集训队加训1)

A.如果钉子与地面距离大于绳子的长度就必须剪

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N],b[N],cl[N];
void Lan(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}ll ans=0;for(int i=1;i<=n;i++){if(a[i]>b[i]){ans++;}}cout<<ans<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}

B.

暴力枚举横竖2个斜

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e3 + 9;
char a[N][N];
void Lan(){for(int i=3;i<=5;i++){for(int j=3;j<=5;j++){cin>>a[i][j];}}for(int i=3;i<=5;i++){for(int j=3;j<=5;j++){if(a[i][j]=='.'){continue;}if(a[i][j]==a[i+1][j+1] && a[i][j]==a[i+2][j+2]){cout<<a[i][j]<<'\n';return;}		if(a[i][j]==a[i+1][j] && a[i][j]==a[i+2][j]){cout<<a[i][j]<<'\n';return;}if(a[i][j]==a[i][j+1] && a[i][j]==a[i][j+2]){cout<<a[i][j]<<'\n';return;}if(a[i][j]==a[i-1][j+1] && a[i][j]==a[i-2][j+2]){cout<<a[i][j]<<'\n';return;}}}cout<<"DRAW"<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}

C.

贪心一下，然后结构体排序即可

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e5 + 9;
ll t[N],prefix[N];
struct node{ll score,t,index;
}a[N];
bool cmp(node a,node b){return (a.score==b.score?(a.t==b.t?a.index<b.index:a.t<b.t):a.score>b.score);//排序
}
void Lan(){int n,m,h;cin>>n>>m>>h;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>t[j];}sort(t+1,t+1+m);//在矩阵中每行排序for(int j=1;j<=m;j++){prefix[j]=prefix[j-1]+t[j];//前缀和}ll res=0;int k;for(k=1;k<=m;k++){if(prefix[k]>h){break;}res+=prefix[k];}a[i].score=k,a[i].t=res,a[i].index=i;//存储}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){//找index==1if(a[i].index==1){cout<<i<<'\n';return;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}

D.

先算不重叠的，再用相似三角形算重合面积

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long double ld;
const int N = 2e5 + 9;
int a[N],diff[N];
void Lan(){ld n,d,h;cin>>n>>d>>h;for(int i=1;i<=n;i++){cin>>a[i];}ld ans=n*d*h/2;for(int i=1;i<=n-1;i++){if(a[i]+h>a[i+1]){diff[i]=a[i]+h-a[i+1];}else{diff[i]=0;}}for(int i=1;i<=n-1;i++){//diff[i]/x=h/d->x*h=d*diff[i];->x=d*diff[i]/hif(diff[i]){ans-=(d*diff[i]/h)*(diff[i])/2;}}cout<<fixed<<setprecision(6)<<ans<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}

E1-E2.

暴力枚举1e6,后面最多到k*k二分即可

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
set<ll> st;
void Lan(){ll n;cin>>n;if(st.count(n)){cout<<"YES"<<'\n';}else{ll x=sqrt(n);if(x>1 && x*(x+1)==n-1){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}}
}
void init(){for(ll i=2;i<=1e6;i++){ll x=1+i+i*i;ll y=i*i;st.insert(x);while(1){if(1.0*y>1.0*1e18/i){break;}y*=i;x+=y;if(x>1e18){break;}st.insert(x);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);init();int q;cin>>q;while (q--) {Lan();}return 0;
}

F.

思路好想的交互，但是写很shi

#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N],c[N],fzc[N];
/*变了就删去不是这个数字的等下一次变把不是这个数字的发送即可不能固定等第2次是否变如果第一次变了不变了第三次变了第四次不变就会wa*/
void Lan(){int n;cin>>n;for(int i=1;i<=9;i++){//初始化!c[i]=0;fzc[i]=0;}for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){//记录现在的数字种类以及数量c[a[i]]++;}cout<<"-"<<" "<<0<<endl;//第一次for(int i=1;i<=n;i++){cin>>a[i];}int keynum=0;//找多的,从少的变到多的for(int i=1;i<=n;i++){fzc[a[i]]++;}for(int i=1;i<=9;i++){if(fzc[i]>c[i]){keynum=i;break;}}if(!keynum){for(int i=1;i<=9;i++){fzc[i]=0;}cout<<'-'<<" "<<0<<endl;//必然要换了	for(int i=1;i<=n;i++){cin>>a[i];	}for(int i=1;i<=n;i++){fzc[a[i]]++;}for(int i=1;i<=9;i++){if(fzc[i]>c[i]){keynum=i;break;}}}vector<int> del;//可以删去的数字for(int i=1;i<=n;i++){if(a[i]!=keynum){del.push_back(i);}}cout<<"-"<<" "<<(int)del.size()<<" ";for(auto &i : del){cout<<i<<" ";}cout<<endl;for(int i=1;i<=9;i++){//清空c[i]=0;fzc[i]=0;}//结束上述过程后数组其实只存在一个数字,因此等2轮找不是这个数字的index即可for(int i=1;i<=n-(int)del.size();i++){//得到数组只是接受一下回复信息cin>>a[i];}ll ansindex=0;for(int i=1;i<=n-(int)del.size();i++){if(a[i]!=keynum){ansindex=i;break;}}if(ansindex){cout<<"!"<<" "<<ansindex<<endl;return;}cout<<"-"<<" "<<0<<endl;//这轮结束后必然会有换的for(int i=1;i<=n-(int)del.size();i++){cin>>a[i];}for(int i=1;i<=n;i++){//找到对应indexif(a[i]!=keynum){ansindex=i;break;}}cout<<"!"<<" "<<ansindex<<endl;
}
int main() {// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}