Problem A 我不会做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=0
补题地址：http://47.96.116.66/problem.php?id=1908
题解：
1、按题意输出，请注意”??(“一起输出, 在评测中会被当成’[‘，所以要分开输出；
2、看清楚什么时候向上取整，什么时候向下取整；
3、二进制1的数量其实有个函数可以用；
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
double nx;
scanf("%lf",&nx);
//nx=(1<<20);
n=nx;
sum=0;
temp=0;
if(nx==0){
cout<<"Areyou";cout<<"sure";cout<<"?";cout<<"?";cout<<")";
cout<<":";cout<<"?";cout<<"?";cout<<"?"<<endl;
continue;
}
while(n){
sum++;
temp+=(n%2);
n/=2;
}
//cout<<sum<<temp<<endl;
if(sum==temp&&sum!=0){
cout<<sum<<endl;
continue;
}else{
n=nx;
if(n!=nx){
n++;
}
}
cout<<"Areyou";
for(int i=1;i<=n;i++){
cout<<"really";
}
cout<<"sure";cout<<"?";cout<<"?";cout<<")";cout<<":";
for(int i=1;i<=n;i++){
cout<<"pardon";
}
cout<<"?";cout<<"?";cout<<"?"<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B 我不能做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=1
补题地址：http://47.96.116.66/problem.php?id=1909
题解：把点离散化出来之后， 把相邻两点之间的线段全部抠出来， 用这些线段建线段树直接维护就好了。
1、整整写了一天（划掉）；
2、扣线段 离散化 例如：所有点以后为1 5 10 应该加点变成 1 2 5 6 10 ，离散化 1([1,1]) 2([2,4]) 3([5,5]) 4([6,9]) 5([10,10])；
PS：点（区间）
3、卡内存，单单找合适的内存设置就搞了半小时；
4、区间更新，需要一点点等差数列的知识，lazy需要两个数组初项（lazy）、公差（tag）；
5、tree数组存储val和左右端点，（为什么代码是op?因为我懒得改，之前和e公用一个结构体）；
6、tree可以偷懒取3倍；
7、少点ll的数组，运算过程ll；
8、想不明白STD的64MB2252MS；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1500000+10;
const int M=500000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum[M*2],Y[N];
char str;
struct node{
int op,l,r;
}e[M];
struct Node{
ll op;
int l,r;
}tree[N*3];
int lazy[N*3];
int tag[N*3];
void pushup(int rt){
tree[rt].op=(tree[rt<<1].op+tree[rt<<1|1].op)%MOD;
}
void pushdown(int rt){
if(lazy[rt]){
//cout<<tree[rt<<1].op<<" "<<tree[rt<<1|1].op<<endl;
//cout<<tree[rt<<1].l<<" "<<tree[rt].r<<" "<<tree[rt<<1|1].l<<" "<<tree[rt].r<<endl;
//cout<<lazy[rt]<<" "<<lazy[rt<<1]<<" "<<lazy[rt<<1|1]<<" "<<endl;
lazy[rt<<1]=(ll)(lazy[rt<<1]+lazy[rt])%MOD;
lazy[rt<<1|1]=(ll)(lazy[rt<<1|1]+lazy[rt]+(ll)(tree[rt<<1|1].l-tree[rt<<1].l)*tag[rt]%MOD)%MOD;
tag[rt<<1]=(ll)(tag[rt<<1]+tag[rt])%MOD;
tag[rt<<1|1]=(ll)(tag[rt<<1|1]+tag[rt])%MOD;
//cout<<lazy[rt<<1]<<" "<<lazy[rt<<1|1]<<" "<<endl;
tree[rt<<1].op = (ll)(tree[rt<<1].op +
((ll)(lazy[rt]-tag[rt])*(tree[rt<<1].r-tree[rt<<1].l+1)%MOD)+
(ll)(tag[rt]*((ll)(tree[rt<<1].r-tree[rt<<1].l+1)*(tree[rt<<1].r-tree[rt<<1].l+2)/2%MOD))%MOD)%MOD;
tree[rt<<1|1].op = (ll)(tree[rt<<1|1].op +
(((lazy[rt]+((ll)(tree[rt<<1|1].l-tree[rt<<1].l)*tag[rt]%MOD)-tag[rt])%MOD)*(tree[rt<<1|1].r-tree[rt<<1|1].l+1)%MOD)+
(tag[rt]*((ll)(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*(tree[rt<<1|1].r-tree[rt<<1|1].l+2)/2)%MOD)%MOD)%MOD;
//cout<<tree[rt<<1].op<<" "<<tree[rt<<1|1].op<<endl;
tag[rt]=0;
lazy[rt]=0;
}
}
void build(int l,int r,int rt){
if(l==r){
tree[rt].l=Y[l];
tree[rt].r=Y[l+1]-1;
tree[rt].op=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
tree[rt].l=tree[rt<<1].l;
tree[rt].r=tree[rt<<1|1].r;
tree[rt].op=0;
pushup(rt);
}
void updata(int l,int r,int rt,int L,int R,ll C){
//cout<<tree[rt].l<<" "<<tree[rt].r<<" "<<tree[rt].op<<" "<<lazy[rt]<<" "<<endl;
if( L <= l && r<= R){
//cout<<C<<endl;
tree[rt].op = (ll)(tree[rt].op+((ll)(tree[rt].l-C)*(tree[rt].r-tree[rt].l+1)%MOD+(((ll)(tree[rt].r-tree[rt].l+1)*(tree[rt].r-tree[rt].l+2)/2)%MOD))%MOD)%MOD; // 染成 c 的颜色
lazy[rt] = (ll)(lazy[rt]+(tree[rt].l-C+1))%MOD;
tag[rt]=(tag[rt]+1)%MOD;
//cout<<tree[rt].op<<endl;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid)updata(l,mid,rt<<1,L,R,C);
if(R>mid) updata(mid+1,r,rt<<1|1,L,R,C);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
//cout<<l<<" "<<r<<" "<<tree[rt].op<<" "<<lazy[rt]<<" "<<tag[rt]<<endl;
if(L <= l && r<= R){
return tree[rt].op;
}
pushdown(rt);
int mid=(l+r)>>1;
ll res=0;
if(L<=mid)res=(res+query(l,mid,rt<<1,L,R))%MOD;
if(R>mid)res=(res+query(mid+1,r,rt<<1|1,L,R))%MOD;
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d",&n,&m);
cnt=0;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].op,&e[i].l,&e[i].r);
sum[++cnt]=e[i].l;
sum[++cnt]=e[i].r;
}
int tot=0;
sort(sum+1,sum+cnt+1);
//X[++tot].l=sum[1],X[tot].r=sum[1];
Y[++tot]=sum[1];
for(int i=2;i<=cnt;i++){
if(sum[i-1]!=sum[i]){
if(sum[i]-sum[i-1]>1){
//X[++tot].l=sum[i-1]+1;
Y[++tot]=sum[i-1]+1;
//X[tot].r=sum[i]-1;
}
//X[++tot].l=sum[i],X[tot].r=sum[i];
Y[++tot]=sum[i];
}
}
Y[tot+1]=Y[tot]+1;
build(1,tot,1);
for(int i=1;i<=m;i++){
int l = lower_bound(Y+1,Y+tot+1,e[i].l)-Y;
int r = lower_bound(Y+1,Y+tot+1,e[i].r)-Y;
//cout<<l<<" "<<r<<endl;
if(e[i].op==1){
updata(1,tot,1,l,r,e[i].l);
}else{
cout<<(query(1,tot,1,l,r)+MOD)%MOD<<endl;
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
/*
10 5
1 1 10
1 1 5
1 6 10
2 1 10
2 5 6
1000000000 5
1 1 1000000000
1 1 500000000
1 500000000 1000000000
2 1 1000000000
2 2 1000000000
*/
Problem C 我想做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=2
补题地址：http://47.96.116.66/problem.php?id=1910
题解：
1、存在i can't't't't't't...的情况，i couldn't同理；
2、存在i can gao ‘t 的情况，i couldn't同理；
3、while多次处理，直到不能进行任何存在；
4、"duxing201606nb!".最后处理；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str0[N],st1[20]="i can't",st2[20]="i couldn't";
string str,str1,str2;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
while(gets(str0)!=NULL){
//scanf("%d",&n);
str=str0;
flag=1;
while(flag){
flag=0;
int pos=0;
while(str[pos]==' ')flag=1,pos++;
str1="";
for(int i=pos;i<str.size();i++){
if(str[i]==' '&&!isalnum(str[i+1])){
flag=1;
continue;
}
str1+=str[i];
}
str2="";
for(int i=0;i<str1.size();i++){
if(i==0&&str1[i]=='g'&&str1[i+1]=='a'&&str1[i+2]=='o'&&!isalnum(str1[i+3])){
flag=1;
i+=2;
continue;
}
if(i&&!isalnum(str1[i-1])&&str1[i]=='g'&&str1[i+1]=='a'&&str1[i+2]=='o'&&!isalnum(str1[i+3])){
flag=1;
i+=2;
continue;
}
if(str1[i]=='i'){
temp=1;
for(int j=0;j<7;j++){
if(str1[i+j]!=st1[j]){
temp=0;
break;
}
}
if(temp){
i+=6;
str2+="i can";
while(str1[i+1]=='\''&&str1[i+2]=='t')
i+=2;
flag=1;
continue;
}
temp=1;
for(int j=0;j<10;j++){
if(str1[i+j]!=st2[j]){
temp=0;
break;
}
}
if(temp){
i+=9;
str2+="i could";
while(str1[i+1]=='n'&&str1[i+2]=='\''&&str1[i+3]=='t')
i+=3;
flag=1;
continue;
}
}
str2+=str1[i];
}
str=str2;
//cout<<str<<endl;
}
str1="";
for(int i=0;i<str.size();i++){
str1+=str[i];
if(str[i]=='.'){
str1+="duxing201606nb!";
}
}
cout<<str1<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem D 我得试着去做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=3
补题地址：http://47.96.116.66/problem.php?id=1911
题解：
线筛求phi，线段树维护a的区间和，由于phi最多执行log次就会变成1，直接暴力维护到叶子节点。判断一下是不是整个区间都是1，是的话就不用继续走了。
1、欧拉函数线性筛；
2、1e7的转换范围内最多18次；
3、线段树优化。
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=500000+10;
const int M=10000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int f[M],prime[M],pre[N];
ll tree[N<<2];
void init(){
f[1]=1;
prime[0]=prime[1]=1;
for(int i=2;i<=1e7;i++){
if(prime[i]==0){
pre[++cnt]=i;
f[i]=i-1;
}
for(int j=1;j<=cnt&&pre[j]*i<=1e7;j++){
prime[i*pre[j]]=1;
f[i*pre[j]]=f[i]*f[pre[j]];
if(i%pre[j]==0){
f[i*pre[j]]=f[i]*(f[pre[j]]+1);
break;
}
}
}
}
void pushup(int rt){
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
scanf("%lld",&tree[rt]);
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void updata(int l,int r,int rt,int L,int R){
if(tree[rt]==r-l+1)
return;
if(l==r){
tree[rt]=f[tree[rt]];
return;
}
int mid=(l+r)>>1;
if(L<=mid)updata(l,mid,rt<<1,L,R);
if(R>mid)updata(mid+1,r,rt<<1|1,L,R);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
if(tree[rt]==r-l+1&&l<=L&&R<=r){
return R-L+1;
}
if(L<=l&&r<=R){
return tree[rt];
}
int mid=(l+r)>>1;
ll res=0;
if(L<=mid)res+=query(l,mid,rt<<1,L,R);
if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
init();
while(~scanf("%d",&n)){
memset(tree,0,sizeof(tree));
build(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&k,&l,&r);
if(k==1){
updata(1,n,1,l,r);
}else{
cout<<query(1,n,1,l,r)<<endl;
}
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem E 我好像不会做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=4
补题地址：http://47.96.116.66/problem.php?id=1912
题解：
对于每一个砖记录下左边可以的第一块砖是哪一块，右边可用的第一块砖是那一块。
在没有取走任何砖的前提下，对于第i块砖来说， l[i] = i-1, r[i] = i+1；
然后我们枚举1-n颜色并且没有被取的砖在那些位置i，拿完之后看一下l[i]\r[i]是不是所需要的砖,如果是就直接拿走，不是就直接从当前位置走到下一个可以取的位置。
在每次拿砖的时候，随时更新L[i], r[i]。
每次经过拿过的砖的时候，将L[i] 和 r[i] 还原为初始值。
这样一直模拟就可以了。
答案为ans*(n-1)+n的位置；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l[N],r[N],u,v;
ll ans,cnt,flag,temp,sum;
int a[N],vis[N],b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d",&n)){
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
l[i]=i-1;
r[i]=i+1;
b[a[i]]=i;
}
ans=0;
for(int i=1;i<=n;i++){
if(vis[i]==0){
int now=i;
ans++;
for(int pos=b[i];pos<=n;b[now]>=r[pos]?pos=b[now]:pos=n+1){
l[pos]=pos-1;
r[pos]=pos+1;
if(a[pos]==now){
vis[now]=1;
now++;
while(a[l[pos]]==now||a[r[pos]]==now){
if(a[l[pos]]==now){
l[pos]--;
vis[now]=1;
now++;
}
if(a[r[pos]]==now){
r[pos]++;
vis[now]=1;
now++;
}
}
}
}
}
}
cout<<ans*n-n+b[n]<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem F 我好像会做了
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=5
补题地址：http://47.96.116.66/problem.php?id=1913
题解：可以通过相似三角形得出线段比值关系，从而证明出反向延长线将三角形分割成两个面积一样的三角形，则该线即是中线交点，初中时老师说过，中线交点是重心，那么，重心交点便是( (x1+x2+x3)/3, (y1+y2+y3)/3 ),最后将坐标答案乘上3的逆元即可。
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
ll x,y,x2,y2,x3,y3;
char str;
struct node{};
ll POW(ll a,ll b,ll c){
ll res=1;
ll base=a%c;
while(b){
if(b&1)res=(res*base)%c;
base=(base*base)%c;
b>>=1;
}
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&x2,&y2,&x3,&y3);
ll X=x+x2+x3;
ll Y=y+y2+y3;
ll inv=POW(3,MOD-2,MOD);
if(X%3==0){
cout<<X/3;
}else{
cout<<(X*inv)%MOD;
}
cout<<" ";
if(Y%3==0){
cout<<Y/3<<endl;
}else{
cout<<(Y*inv)%MOD<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem G 我会尽量做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=6
补题地址：http://47.96.116.66/problem.php?id=1914
题解：
1、map；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
int b[N];
char str[10];
map<string,int>mp;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s%d",str,&t);
if(!mp[str])mp[str]=++cnt;
a[mp[str]]=t;
}
//cout<<cnt<<endl;
for(int i=1;i<=m;i++){
scanf("%d%s%d",&k,str,&t);
if(k==1){
b[mp[str]]=max(t,b[mp[str]]);
}else{
a[mp[str]]+=t;
}
}
for(int i=1;i<=cnt;i++){
if(a[i]<=b[i])
ans++;
}
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem H 我能做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=7
补题地址：http://47.96.116.66/problem.php?id=1915
C++版本一
题解：暴力方法（数据弱）
1、标记这个员工有没有工作；
2、向查询boss有没有工作并求最小值；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=50000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,op;
int ans,cnt,flag,temp,sum;
bool vis[N];
struct node{};
int pre[N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
while(~scanf("%d%d",&n,&m)){
for(int i=i;i<=n;i++)pre[i]=i;
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++){
scanf("%d",&u);
pre[i]=u;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&op,&u);
if(op==1){
vis[u]=1;
}else if(op==2){
vis[u]=0;
}else{
ans=INF;
while(pre[u]!=u){
if(vis[u]){
ans=min(ans,u);
}
u=pre[u];
}
if(vis[u]){
ans=min(ans,u);
}
cout<<(ans==INF?-1:ans)<<endl;
}
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：
线段树维护子树。
先求出dfs序。
每次1 X的时候，都往 in[x] out[x]这段区间内插入x
每次2 X的时候，都从 in[x] out[x]这段区间内删除x
每次3 X的时候，和李超树类似，在包含这个in[x]的所有区间中找到最小值。
最小值用set去维护。
最后的复杂度就是O(n*logn*logn).
Problem I 我会做
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=8
补题地址：http://47.96.116.66/problem.php?id=1916
题解：（真心看不懂题解，怕不是体育老师教的语文？）
可以先将偶数位置设定为自己选取，奇数位置为对方选取。然后，我们发现，第i位，可以与之后（i到n）的一个对方选取的物品进行交换，交换之后还满足之前的性质。那么这个过程可以用线段树或者multiset之类的完成。
当然，也可以用优先队列什么的乱搞，倒着模拟。
C++版本一
题解：优先队列
从后往前取的模拟，奇数位置的就放优先队列里，然后偶数位置的话就和优先队列里最大的比，如果小于的话，就把最大那个加进答案，然后删除，再把偶数位的那个放进去，大于就直接放原来偶数位的，说白了就是第i位，要比后面任何一奇数位大；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{
ll id,val;
bool operator <(const node &S)const{
if(val==S.val){
return id>S.id;
}
return val<S.val;
}
}x;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d",&n)){
ans=0;
priority_queue<node>q;
while(!q.empty()){
q.pop();
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=n;i>=1;i--){
if(i%2==0){
if(!q.empty()&&q.top().val>a[i]){
x=q.top();
q.pop();
swap(a[i],x.val);
q.push(x);
}
ans+=a[i];
}else{
x.id=i;
x.val=a[i];
q.push(x);
}
}
cout<<ans<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
线段树+结构体
（快还是优先队列快一点）
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{
ll id,val;
bool operator <(const node &S)const{
if(val==S.val){
return id>S.id;
}
return val<S.val;
}
}tree[N<<2],x;
void pushup(int rt){
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
tree[rt].id=l;
tree[rt].val=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void updata(int l,int r,int rt,int L,ll C){
if(l==r){
tree[rt].val=C;
return;
}
int mid=(l+r)>>1;
if(L<=mid)updata(l,mid,rt<<1,L,C);
else updata(mid+1,r,rt<<1|1,L,C);
pushup(rt);
}
node query(int l,int r,int rt,int L,int R){
if(L<=l&&r<=R){
return tree[rt];
}
int mid=(l+r)>>1;
node res;
res.val=0;
if(L<=mid)res=max(res,query(l,mid,rt<<1,L,R));
if(R>mid)res=max(res,query(mid+1,r,rt<<1|1,L,R));
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d",&n)){
ans=0;
build(1,n,1);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=n;i>=1;i--){
if(i%2==0){
x=query(1,n,1,i,n);
if(x.val>a[i]){
updata(1,n,1,x.id,a[i]);
a[i]=x.val;
}
ans+=a[i];
}else{
updata(1,n,1,i,a[i]);
}
}
cout<<ans<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本三
multiset我是真不会
Problem J 我做到了
比赛地址：http://47.96.116.66/problem.php?cid=1222&pid=9
补题地址：http://47.96.116.66/problem.php?id=1917
题解：我们可以随便在纸上画出一些点，如果我们用一个定长圆去套这些点，我们可以发现，圆上至少有两个点，则我们可以得出，最大值一定在任意两个点确定的半径为r的圆内，那我我们可以n^2枚举出所有圆心，判断剩下n-2个点是否在圆内，更新美味度的最大值即可，注意，枚举圆上的两个点时候，注意判断两个点之间距离是否能够组成一个半径为r的圆，以及两个点可以确定1~2个圆。
1、百度的方法求圆心是不行的（精度原因），正确方法是用斜率求出相对于枚举的两个点的中点的增量dx dy；
2、long double是错的；
3、枚举的两个点纵坐标相同时需要特判；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
char str;
struct node{
ll x,y,v;
}e[N];
double dist(double x,double y,double x2,double y2){
return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
ll sloved(int i,int j){
if(dist(e[i].x,e[i].y,e[j].x,e[j].y)>2*r){
return 0;
}
double x1 = e[i].x, y11 = e[i].y, x2 = e[j].x, y2 = e[j].y, R = r;
double y01 = 0, x01 = 0, x02 = 0, y02 = 0;
if(y11==y2){
x02=x01=(x1+x2)/2;
y01=sqrt(R*R-(x1-x2)*(x1-x2)/4)+y11;
y02=-sqrt(R*R-(x1-x2)*(x1-x2)/4)+y2;
}else{
double dis=dist(x1,y11,x2,y2)/2;
double k=-(x1-x2)/(y11-y2);
double d=sqrt(R*R-dis*dis);
double x0=(x1+x2)/2,y0=(y11+y2)/2;
double dy=sin(atan(k))*d,dx=cos(atan(k))*d;
x01=x0+dx;
y01=y0+dy;
x02=x0-dx;
y02=y0-dy;
}
ll res0=0;
//cout<<i<<" "<<j<<endl;
//cout<<x01<<" "<<y01<<endl;
for(int i=1;i<=n;i++){
if(dist(x01,y01,e[i].x,e[i].y)<=R){
res0+=e[i].v;
}
}
ll res1=0;
for(int i=1;i<=n;i++){
if(dist(x02,y02,e[i].x,e[i].y)<=R){
res1+=e[i].v;
}
}
return max(res0,res1);
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d%d",&n,&r)){
ans=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].v);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ans=max(ans,sloved(i,j));
}
}
cout<<ans<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号