A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
int a,b;
cin >> a >> b;
if(a^b){
if(a==1) cout << "Yes\n";
else cout << "No" << '\n';
}
else cout << "Invalid\n";
}
system("color 04");
return 0;
}
B
问从s变到t,每次可以变s中的一个字母,找到一个字典序最小的方案,首先可以从左到右枚举变哪一个,我们想要字典序最小,每次要变,\(si>ti\),如果没找到,则变\(si<ti\)。时间复杂度\(O(N^2)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
string s,t;
cin >> s >> t;
vector<string> ans;
while(s!=t){
bool ok=0;
fors(i,0,s.size()-1){
if(s[i]>t[i]){
s[i]=t[i];
ok=1;
break;
}
}
if(!ok){
forr(i,0,s.size()-1){
if(s[i]<t[i]){
s[i]=t[i];
break;
}
}
}
ans.push_back(s);
}
cout << ans.size() << '\n';
if(ans.size()) fors(i,0,ans.size()-1) cout << ans[i] << '\n';
}
system("color 04");
return 0;
}
C
模拟
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
int n;
cin >> n;
vector<vector<int>> a(n+1,vector<int>(n+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> a[i][j];
a[j][i]=a[i][j];
}
}
int ans=1;
for(int i=1;i<=n;i++) ans=a[ans][i];
cout << ans << '\n';
}
system("color 04");
return 0;
}
D
二分查找,如果(x,y)这个格子存在直接删除,否则需要找到第x行大于y的第一个元素,小于y的第一个元素,第y列大于x的第一个元素,小于x的第一个元素,可以用set实现,时间复杂度\(O(Q*log)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
int n,m,q;
cin >> n >> m >> q;
vector<set<int>> a(n+1),b(m+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i].insert(j);
b[j].insert(i);
}
}
int ans=n*m;
while(q--){
int x,y;
cin >> x >> y;
if(a[x].count(y)){
ans--;
a[x].erase(y);
b[y].erase(x);
}
else{
auto it=a[x].lower_bound(y);
if(it!=a[x].begin()){
int p=*prev(it);
ans--;
a[x].erase(p);
b[p].erase(x);
}
if(it!=a[x].end()){
int p=*it;
ans--;
a[x].erase(p);
b[p].erase(x);
}
it=b[y].lower_bound(x);
if(it!=b[y].begin()){
int p=*prev(it);
ans--;
a[p].erase(y);
b[y].erase(p);
}
if(it!=b[y].end()){
int p=*it;
ans--;
a[p].erase(y);
b[y].erase(p);
}
}
}
cout << ans << '\n';
}
system("color 04");
return 0;
}
E
dp f(i)表示以i结尾的合法的划分方案,如果不考虑k,\(f_i+=\sum_{j=1}^{i-1}f_j\,\,\,\),可以用一个变量记录前缀和。现在考虑k,需要再减去一个等于k的方案数,维护一个dpj [j+1,i]和等于k的方案数,前缀和si-sj=k,sj=si-k,sj是一个固定值,用一个map维护就可以。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=998244353,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
int n,k;
cin >> n >> k;
vector<int> a(n+1),pre(n+1),f(n+1);
map<int,int> mp;
fors(i,1,n) cin >> a[i],pre[i]=pre[i-1]+a[i];
mp[0]=1;
f[0]=1;
int sum=1;
fors(i,1,n){
f[i]=(sum-mp[pre[i]-k]+mod)%mod;
mp[pre[i]]=(mp[pre[i]]+f[i])%mod;
sum=(sum+f[i])%mod;
}
cout << f[n] << '\n';
}
system("color 04");
return 0;
}
F
看到最小值最大,不难想到二分,主要是check函数怎么写,如果说是链的情况很简单直接贪心分段每段的长度>=x,看是否能分成k段,现我们可以开俩倍长度的数组进行破环成链,我们可以先放几块板子,满足各段区间和大于等于x,俩个板子的位置为i和j,如果板子i移动到j位置,则j会移动到下一个板子所在的位置。就会得到一个图论问题,i->j连一条边,j到下一个板子连一条边。可以用到倍增预处理出来,g(i,j),表示从i开始走\(2^j\)步到达的板子位置,最后我们只需要看最后一块板子是不是小于等于i+n。时间复杂度\(O(n*log*log)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=998244353,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
return rand()%r+l;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int __=1;
// cin >> __;
while(__--){
int k,n;
cin >> n >> k;
vector<int> a(2*n+1),pre(2*n+1);
fors(i,1,n) cin >> a[i],a[i+n]=a[i];
fors(i,1,2*n) pre[i]=pre[i-1]+a[i];
auto check=[&](int x)->int{
vector<vector<int>> f(2*n+2,vector<int>(20,2*n+1));
for(int i=1,j=1;i<=2*n;i++){
while(j<=2*n&&pre[j]-pre[i-1]<x) j++;
if(j<=2*n) f[i][0]=j+1;
else f[i][0]=j;
}
fors(j,1,19){
fors(i,1,2*n){
f[i][j]=f[f[i][j-1]][j-1];
}
}
int cnt=0;
fors(i,1,n){
int cur=i;
forr(j,0,19){
if(k>>j&1){
cur=f[cur][j];
if(cur>i+n) break;
}
}
if(cur<=i+n) cnt++;
}
return cnt;
};
int l=1,r=1e10;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << l << ' ' << n-check(l) << '\n';
}
system("color 04");
return 0;
}
标签:__,AtCoder,typedef,int,题解,cin,long,370,define
From: https://www.cnblogs.com/stability/p/18402774