做女朋友的网站,推广信息哪个平台好,爱站关键词挖掘,找工作58同城最新招聘附近A - Bad Triangle
选出三个序列使之不能组成三角形。先把差距最大的选了#xff0c;枚举中间值。两边之和不大于第三边。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeiostream
#includealgorithm
using namespace std;
const i…A - Bad Triangle
选出三个序列使之不能组成三角形。先把差距最大的选了枚举中间值。两边之和不大于第三边。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeiostream
#includealgorithm
using namespace std;
const int N50010;
int a[N];
int main()
{IO;int T;cinT;while(T--){int n;cinn;for(int i1;in;i) cina[i];int i;for(i2;in;i) if(a[1]a[i]a[n])break;if(in) cout-1endl;else cout1 i nendl;}return 0;
}B - Substring Removal Game
第一次没加#includevector还Compilation error了。。 考虑原串中连续的1。两人一定轮流选择目前连续1个数最多的。把连续的1个数存到一个数组逆序。两人轮流取即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includestring
#includevector
#includecstring
#includeiostream
#includealgorithm
using namespace std;
const int N110;
int a[N];
int main()
{IO;int T;cinT;while(T--){string s;cins;int ns.size();vectorint ans(n);for(int i1;in;i) a[i]s[i-1]-0;for(int i1;in;i){int ji;while(jna[i]a[j]) j;if(a[i]1) ans.push_back(j-i);ij-1;}int res0;sort(ans.begin(),ans.end());reverse(ans.begin(),ans.end());for(int i0;ians.size();i) if(i%20) resans[i];coutresendl;}return 0;
}C - Good Subarrays
对于原数组a[l1]a[l2]⋯a[r]r−l1a[l1]a[l2]\dotsa[r]r-l1a[l1]a[l2]⋯a[r]r−l1考虑前缀和数组即a[r]−a[l]r−la[r]-a[l]r-la[r]−a[l]r−l变换一下a[r]−ra[l]−la[r]-ra[l]-la[r]−ra[l]−l。因此只需统计a[i]−ia[i]-ia[i]−i的个数根据组合数的计算公式即可。由于可能有负数弄了个map映射。上述情况未考虑i0的情况因此最后应加上a[i]i的个数。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstdio
#includestring
#includemap
#includevector
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N100010;
int a[N];
mapint,int mp;
int idx0;
int get(int s)
{if(!mp.count(s)) mp[s]idx;return mp[s];
}
ll cnt[N];
int main()
{IO;int T;cinT;while(T--){int n;cinn;mp.clear();for(int i0;in;i) cnt[i]0;idx0;string s;cins;for(int i1;in;i) a[i]s[i-1]-0;for(int i1;in;i) a[i]a[i-1];for(int i1;in;i) cnt[get(a[i]-i)];ll res0;for(int i1;iidx;i) res1ll*cnt[i]*(cnt[i]-1)/2;for(int i1;in;i)if(a[i]i) res;coutresendl;}return 0;
}这题很快就想到怎么写了但是码代码能力还是不行写了半天。最开始没想用map弄明白数组开多大烦死了负数可以平移然后就用map了。看群里讨论发现负数不一定平移可以为负数多开一个数组记录a[-i],i0。
D - Colored Rectangles
首先贪心对于每一对木条肯定选择长的。因此先降序排列数组。 f[i][j][k]表示R用了i个G用了j个B用了k个的集合。转移考虑最后用的是那一对木棒。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstdio
#includestring
#includemap
#includevector
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N210;
int a[N],b[N],c[N];
int f[N][N][N];
int cnta,cntb,cntc;
int main()
{IO;cincntacntbcntc;for(int i1;icnta;i) cina[i];for(int i1;icntb;i) cinb[i];for(int i1;icntc;i) cinc[i];sort(a1,a1cnta);sort(b1,b1cntb);sort(c1,c1cntc);reverse(a1,a1cnta);reverse(b1,b1cntb);reverse(c1,c1cntc)for(int i0;icnta;i)for(int j0;jcntb;j)for(int k0;kcntc;k){if(ij(ijk)%20) f[i][j][k]max(f[i][j][k],f[i-1][j-1][k]a[i]*b[j]);if(jk(ijk)%20) f[i][j][k]max(f[i][j][k],f[i][j-1][k-1]c[k]*b[j]);if(ik(ijk)%20) f[i][j][k]max(f[i][j][k],f[i-1][j][k-1]a[i]*c[k]);}int res0;for(int i0;icnta;i) resmax(res,f[i][cntb][cntc]);for(int i0;icntb;i) resmax(res,f[cnta][i][cntc]);for(int i0;icntc;i) resmax(res,f[cnta][cntb][i]);coutresendl;return 0;
}D题最后1分钟提交的太惊险了。
E-Two Types of Spells
群里大佬说是权值线段树离散化这个我学过补一下吧。 如果有k个lightning那么能过翻倍k-1或者k个伤害讨论一下翻倍肯定翻倍最大的几个因此考虑权值线段树因此需要离散化维护前k大一般有删除加入需要用set维护数据无重复让题目简单不少。 lower_bound只能够在升序情况下使用
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstdio
#includestring
#includemap
#includeset
#includevector
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010;
int n;
pii q[N];
vectorint id;
struct node
{int l,r,cnt;ll sum;
}tree[N*4];
int get(int a)
{int l0,rid.size()-1;while(lr){int midlr1;if(id[mid]a) rmid;else lmid1;}return l1;
}
void pushup(int u)
{tree[u].cnttree[u1].cnttree[u1|1].cnt;tree[u].sumtree[u1].sumtree[u1|1].sum;}
void build(int u,int l,int r)
{tree[u]{l,r,0,0};if(lr) return;int midlr1;build(u1,l,mid),build(u1|1,mid1,r);
}
void modify(int u,int k,int x)
{if(tree[u].ltree[u].r){tree[u].cntx;tree[u].sumx*id[k-1];return;}int midtree[u].ltree[u].r1;if(kmid) modify(u1,k,x);else modify(u1|1,k,x);pushup(u);
}
ll query(int u,int k)
{if(tree[u].ltree[u].r) return tree[u].sum;int tmptree[u1].cnt;if(tmpk) return query(u1,k);else return tree[u1].sumquery(u1|1,k-tmp);
}
int main()
{IO;cinn;build(1,1,n);for(int i1;in;i){cinq[i].firstq[i].second;id.push_back(abs(q[i].second));}sort(id.begin(),id.end());id.erase(unique(id.begin(),id.end()),id.end());reverse(id.begin(),id.end());setint fire,lightning;int k0;ll res0;for(int i1;in;i){if(q[i].first1){if(q[i].second0){k;lightning.insert(q[i].second);resq[i].second;modify(1,get(q[i].second),1);}else{k--;lightning.erase(-q[i].second);resq[i].second;modify(1,get(-q[i].second),-1);}}else{if(q[i].second0){fire.insert(q[i].second);resq[i].second;modify(1,get(q[i].second),1);}else{fire.erase(-q[i].second);resq[i].second;modify(1,get(-q[i].second),-1);}}if(fire.empty()){if(k1)coutresquery(1,k-1)\n;else coutres\n;}else if(lightning.empty()) coutres\n;else{int minl*lightning.begin();auto tfire.end();t--;int maxf*t;if(minlmaxf){if(k1) coutresquery(1,k-1)maxf\n;else coutresmaxf\n;}else{if(k0) coutresquery(1,k)\n;else coutres\n;}}}return 0;
}要加油哦~
