ab略...
C:
map嵌套水过去的，复杂度\(nlog^2n\),感觉不如正解
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 2e5+100;
int a[maxn];bool vis[maxn];
signed main() {
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int n;cin>>n;
map<int,int>mp,mp2;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int x=1;
int m;cin>>m;string s;
while(m--){
x=1;cin>>s;
mp.clear();mp2.clear();
if(s.size()==n){
for(int i=0;i<n;i++){
//cout<<a[i+1]<<' ';
if(mp[a[i+1]]==0){
mp[a[i+1]]=(s[i]-'0')+1e9+7;
if(mp2[mp[a[i+1]]]==0){
mp2[mp[a[i+1]]]=a[i+1]+1e9+7;
}
else{
x=0;break;
}
}
else if((mp[a[i+1]]-1e9-7)!=(s[i]-'0')){
x=0;break;
}
}
}
else x=0;
if(x)cout<<"YES"<<"\n";
else cout<<"NO"<<"\n";
}
}
}
D:
猜结论猜了一个每次选左右最大的区间，然后双指针结束。还是比较好理解的吧，因为存在大区间可取的情况下取小区间一定不优。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 2e5+100;
int pre[maxn];
int a[maxn];bool vis[maxn];
signed main() {
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];pre[i]=pre[i-1]+a[i];
}
string s;cin>>s;
int l=0,r=n-1;bool x=1;
for(int i=1;i<n;i++){
if(s[i]!=s[i-1])x=0;
}
if(x){
cout<<0<<"\n";
continue;
}
int ans=0;
while(l<r){
if(s[l]=='L'&&s[r]=='R'){
ans+=pre[r+1]-pre[l];
l++;r--;
}
if(s[l]!='L')l++;
if(s[r]!='R')r--;
}
cout<<ans<<"\n";
}
}
E:
一开始以为复杂度是2e5*2e5，后来发现只有2e5...一个星星最多会算k^2次，但是因为只有2e5所以可以直接暴力求每个格子的次数然后分配给星星（排序两次即可。。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 2e5+10;
int pre[maxn];
int a[maxn],p[maxn],tot;
signed main() {
ios::sync_with_stdio(false);
// ½â³ýcinºÍcoutµÄĬÈϰ󶨣¬À´½µµÍIOµÄ¸ºµ£Ê¹Ð§ÂÊÌáÉý
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int n,m,k;cin>>n>>m>>k;
int w;cin>>w;tot=0;
for(int i=1;i<=w;i++){
cin>>a[i];
}
sort(a+1,a+w+1);reverse(a+1,a+w+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int lu=min(i,n-k+1),ru=max(1LL*0,i-k);
int lm=min(j,m-k+1),rm=max(1LL*0,j-k);
p[++tot]=(ru-lu)*(rm-lm);
}
}
sort(p+1,p+tot+1);reverse(p+1,p+tot+1);
int sum=0;
for(int i=1;i<=w;i++){
sum+=p[i]*a[i];
}
cout<<sum<<"\n";
}
}
F:
一开始以为选短的边最优，写完了最后一个样例没过，才发现思路假了，应该dp（看数据范围就应该知道但是我每次都看错数据范围）。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 1005;
int pre[maxn];
int a[maxn],dp[maxn][105],g[maxn];
signed main() {
ios::sync_with_stdio(false);
// ½â³ýcinºÍcoutµÄĬÈϰ󶨣¬À´½µµÍIOµÄ¸ºµ£Ê¹Ð§ÂÊÌáÉý
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int n,k;cin>>n>>k;
for(int j=1;j<=k;j++)
dp[0][j]=0x3f3f3f3f;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
int c=x,r=y;
for(int j=1;j<=x+y;j++){
if(c<=r){
g[j]=g[j-1]+c;
r--;
}
else{
g[j]=g[j-1]+r;c--;
}
}
for(int j=1;j<=k;j++){
dp[i][j]=0x3f3f3f3f;
for(int nw=0;nw<=min(j,x+y);nw++){
dp[i][j]=min(dp[i][j],dp[i-1][j-nw]+g[nw]);
}
//cout<<dp[i][j]<<"\n";
}
}
if(dp[n][k]==0x3f3f3f3f)cout<<-1<<"\n";
else cout<<dp[n][k]<<"\n";
}
}
G:
很普通的最短路题，dijkstra就跑过了，以n为起点然后往1跑（因为终止时间是确定的，起始时间不确定），过程中判断一下是否在打电话即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 1e5+10;
vector<pair<int,pii> >g[maxn];
int dis[maxn];bool vis[maxn];
signed main() {
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int n,m;cin>>n>>m;
int t0,t1,t2;cin>>t0>>t1>>t2;
for(int i=0;i<=max(n,m);i++)dis[i]=-1e9,vis[i]=0,g[i].clear();
while(m--){
int u,v,l1,l2;cin>>u>>v>>l1>>l2;
g[u].push_back(mkp(v,mkp(l1,l2)));
g[v].push_back(mkp(u,mkp(l1,l2)));
}
set<pii>q;
dis[n]=t0;q.insert(mkp(t0,n));
while(!q.empty()){
pii p=*q.rbegin();q.erase(p);
int u=p.sec,d=p.fir;
if(vis[u])continue;
vis[u]=1;
for(auto i:g[u]){
int v=i.fir,l1=i.sec.fir,l2=i.sec.sec;
int d1;
if(d<=t1||d-l1>=t2)d1=d-l1;
else d1=max(d-l2,t1-l1);
if(d1>dis[v]){
dis[v]=d1;
q.insert(mkp(dis[v],v));
}
}
}
if(dis[1]>=0)cout<<dis[1]<<"\n";
else cout<<-1<<"\n";
}
}
H:
还没看
总结：div3还是div3，但是能ak div3说明对数据结构有一些基本掌握而且代码熟练，我这种菜狗也是做不到的，还得加练。
标签：966,cout,int,cin,Codeforces,maxn,mkp,Div,define From： https://www.cnblogs.com/lyrrr/p/18395241