tot：赛时是6题723罚时，还是差劲了。省赛，特别是这场省赛，难度低很多。前面4，5题都是签到题。第六题是一个关于闰年的容斥，脑子乱了，然后越来越绕。然后就没出。出的是一个诈骗题，题面引导你这是计算几何，但是实际上是简单dp，暴力o(n^2)预处理一下就行了。赛时还想着求凸包然后旋转卡壳求凸包直径来预处理，再dp，但是这样是o(n^3)的，然后过了不知道多久突然才发现完全用不上计算几何，直接最普通的枚举区间取max就可以预处理出来了。然后赛后再补了闰年的容斥和一题挺典型的题目，共计8题。
2024CCPC辽宁省赛.pdf
比分幻术
思路：签到。
string str;
void solve(){
cin>>str;
cout<<str[2]<<str[1]<<str[0];
}爱上字典
思路：签到。
string str;
int n;
string toLower(string s){
int len=(int)s.size();
string res="";
for(int i=0;i<len;i++){
if(s[i]>='A'&&s[i]<='Z') res+=s[i]+32;
else res+=s[i];
}
return res;
}
void solve(){ //A
getline(cin,str);
str=toLower(str);
cin>>n;
unordered_map<string,bool> mp;
for(int i=1;i<=n;i++){
string s; cin>>s;
mp[toLower(s)]=true;
}
string cur="";
int ans=0;
for(int i=0;i<(int)str.size();i++){
if(str[i]>='a'&&str[i]<='z') cur+=str[i];
else if(cur!=""){
if(!mp[cur]) ans++,mp[cur]=true;
cur="";
}
}
cout<<ans;
}结课风云
思路：签到。
int n,a,b,c,d;
int x[1003],y[1003];
void solve(){ //J
cin>>n>>a>>b>>c;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
cin>>d;
int ans=0;
for(int i=1;i<=n;i++){
if(x[i]+y[i]>=c) continue;
x[i]=min(a,x[i]+d);
if(x[i]+y[i]>=c) ans++;
}
cout<<ans;
}
插排串联
思路：用multiset存一下每个排插的大小，然后在回溯的时候判断是否有满足条件的排插即可。
int n;
int arr[100005];
vector<int> vct[100005];
multiset<int> st; //用了set,给去重了。。不能去重。。
bool ans=true;
int dfs(int s){
if((int)vct[s].size()==0) return arr[s];
int res=0;
for(auto v:vct[s]) res+=dfs(v);
if(s==0&&res>2200) ans=false;
else if(s==0) return 0;
auto p=st.lower_bound(res);
if(p==st.end()) ans=false;
else st.erase(p);
return res;
}
void solve(){ //C
cin>>n;
for(int i=1;i<=n;i++){
int x; cin>>x>>arr[i];
vct[x].emplace_back(i);
}
for(int i=1;i<=n;i++) if((int)vct[i].size()!=0) st.emplace(arr[i]);
dfs(0);
ans?cout<<"YES":cout<<"NO";
}都市叠高
思路：题目误导你这题是计算几何，实则只是普通的dp。一开始的确被误导了，很后面才反应过来o(n^2)就能预处理出要的信息了。简单dp。
int n;
typedef struct Point{
int x,y;
}Point;
Point point[5005];
double dist(Point a,Point b){ return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ); }
double dp[5005];
double mx[5005][5005]; //dist[i][j]定义为:从i往后连续j个构成的凸包直径.
void solve(){
cout<<setprecision(10);
cin>>n;
for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].y;
for(int i=1;i<=n;i++){
double mx0=0;
for(int j=i+1;j<=n;j++){
mx0=max(mx0,dist(point[i],point[j]));
mx[i][j]=mx0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]=max(dp[i],dp[i-j]+mx[i-j+1][i]);
}
}
cout<<dp[n];
}俄式简餐
思路：队友写的构造。注意判6的情况就行。
void solve(){ //E
int n, m;
cin >> n >> m;
vector g(n + 10, vector<int>(m + 10));
int cnt = 1;
if (n == 2 && m == 2 || n * m % 4) {
cout << "NO" << endl;
return ;
}
if (n % 4 == 0) {
for (int j = 1; j <= m; j ++) {
for (int i = 1; i <= n; i += 4) {
g[i][j] = g[i + 1][j] = g[i + 2][j] = g[i + 3][j] = cnt;
cnt ++;
}
}
} else if (m % 4 == 0) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j += 4) {
g[i][j] = g[i][j + 1] = g[i][j + 2] = g[i][j + 3] = cnt;
cnt ++;
}
}
} else if ( n % 2 == 0 && m % 2 == 0) {
if (n % 6 == 0) {
for (int j = 1; j <= m; j += 2) {
for (int i = 1; i <= n; i += 6) {
g[i][j] = g[i][j + 1] = g[i + 1][j] = g[i + 2][j] = cnt++;
g[i + 3][j] = g[i + 4][j] = g[i + 5][j] = g[i + 5][j + 1] = cnt ++;
g[i + 1][j + 1] = g[i + 2][j + 1] = g[i + 3][j + 1] = g[i + 4][j + 1] = cnt ++;
}
}
} else if (n % 6 == 4) {
for (int j = 1; j <= m; j += 2) {
for (int i = 1; i <= n - 4; i += 6) {
g[i][j] = g[i][j + 1] = g[i + 1][j] = g[i + 2][j] = cnt++;
g[i + 3][j] = g[i + 4][j] = g[i + 5][j] = g[i + 5][j + 1] = cnt ++;
g[i + 1][j + 1] = g[i + 2][j + 1] = g[i + 3][j + 1] = g[i + 4][j + 1] = cnt ++;
}
}
for (int j = 1; j <= m; j ++) {
g[n][j] = g[n - 1][j] = g[n - 2][j] = g[n - 3][j] = cnt;
cnt ++;
}
} else if (m % 6 == 0) {
for (int i = 1; i <= n; i += 2) {
for (int j = 1; j <= m; j += 6) {
g[i][j] = g[i + 1][j] = g[i][j + 1] = g[i][j + 2] = cnt++;
g[i][j + 3] = g[i][j + 4] = g[i][j + 5] = g[i + 1][j + 5] = cnt ++;
g[i + 1][j + 1] = g[i + 1][j + 2] = g[i + 1][j + 3] = g[i + 1][j + 4] = cnt ++;
}
}
} else if (m % 6 == 4) {
for (int i = 1; i <= n; i += 2) {
for (int j = 1; j <= m - 4; j += 6) {
g[i][j] = g[i + 1][j] = g[i][j + 1] = g[i][j + 2] = cnt++;
g[i][j + 3] = g[i][j + 4] = g[i][j + 5] = g[i + 1][j + 5] = cnt ++;
g[i + 1][j + 1] = g[i + 1][j + 2] = g[i + 1][j + 3] = g[i + 1][j + 4] = cnt ++;
}
}
for (int i = 1; i <= n; i ++) {
g[i][m] = g[i][m - 1] = g[i][m - 2] = g[i][m - 3] = cnt;
cnt ++;
}
} else if (n % 4 == 2 && n != 2) {
for (int j = 1; j <= m; j ++) {
for (int i = 1; i <= n - 6; i += 4) {
g[i][j] = g[i + 1][j] = g[i + 2][j] = g[i + 3][j] = cnt ++;
}
}
for (int j = 1; j <= m; j += 2) {
g[n - 5][j] = g[n - 4][j] = g[n - 3][j] = g[n - 5][j + 1] = cnt ++;
g[n - 2][j] = g[n - 1][j] = g[n][j] = g[n][j + 1] = cnt ++;
g[n - 4][j + 1] = g[n - 3][j + 1] = g[n - 2][j + 1] = g[n - 1][j + 1] = cnt ++;
}
} else if (m % 4 == 2) {
// cout << "------" << endl;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m - 6; j += 4) {
g[i][j] = g[i][j + 1] = g[i][j + 2] = g[i][j + 3] = cnt;
cnt ++;
}
}
for (int i = 1; i <= n; i += 2) {
g[i][m - 5] = g[i][m - 4] = g[i][m - 3] = g[i + 1][m - 5] = cnt ++;
g[i][m - 2] = g[i][m - 1] = g[i][m] = g[i + 1][m] = cnt ++;
g[i + 1][m - 4] = g[i + 1][m - 3] = g[i + 1][m - 2] = g[i + 1][m - 1] = cnt ++;
}
}
}
cout << "YES" << endl;
// return ;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cout << g[i][j] << ' ';
}
cout << endl;
}
}龙之研习
思路：
n 整除 4×100^p 但不整除 100^(p+1);
式子①:x/4*100^p;
式子②:x/100^(p+1);
这里①是:x整除4*100^p的都是闰年,但是其中②是平年,所以要减去.
同时,②还有去重的作用,因为下一个p是:x/4*100^(p+1),这里的x/4*100^(p+1)按理来说已经被上一个算过了
但是因为上一个同时还有②,那么会把属于x/4*100(p+1)的部分给减去了,同时更高次方的也会减去..
其他的次方是同理的,如此下来,是没有算重算漏的.
int n;
inline int cal(int x){ //计算2025~x的平年的个数
int run=0,run0=0,x0=2024,q=1;
for(int p=0;p<=8;p++){
// n 整除 4×100^p 但不整除 100^(p+1);
//式子①:x/4*100^p;
//式子②:x/100^(p+1);
//这里①是:x整除4*100^p的都是闰年,但是其中②是平年,所以要减去.
//同时,②还有去重的作用,因为下一个p是:x/4*100^(p+1),这里的x/4*100^(p+1)按理来说已经被上一个算过了
//但是因为上一个同时还有②,那么会把属于x/4*100(p+1)的部分给减去了,同时更高次方的也会减去..
//其他的次方是同理的,如此下来,是没有算重算漏的.
run+=x/(4*q)-x/(q*100);
run0+=x0/(4*q)-x0/(q*100);
q*=100;
}
return (x-run)-(x0-run0);
}
void solve(){
cin>>n;
int l=2025,r=4e18,ans=-1;
while(l<=r){
int mid=(l+r)>>1ll;
if(cal(mid)>=n){ //这里得是>=号,不然可能取不到最小值..也不能直接对(ans,mid)取min.
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
}顾影自怜
思路：
不懂不懂..没思路...一开始想着很混乱,最大值是不同数字,又是隔开的,又是区间的,还要满足k个..晕.. key:这个时候就要考虑,需要什么信息?可以预处理出来吗? ①也不难..可以"预处理"之后,o(1)知道每个数字左边和右边第一个比它大的位置. ②也可以o(1)知道每个数字从此位置起,往右直至其出现k次的位置在哪里. ③还可以维护每个数字,上一次出现的位置. 有了以上三个信息,可以枚举"每个位置作为第一个最大值"时,可以得到的贡献. 即合法的左区间为(max(lmx,last),i],合法的右区间为[nex,rmx). last为上一个当前数字的位置,nex第k次出现当前数字的位置. key:其实以前做过类似的题,应该是st表写的.也是只考虑每个点,对全部右区间的贡献,而对于左区间,只考虑到上一个当前数字为止. 这样就不会算重算漏. ps:这题的官方题解是有问题的..
int n,k;
int arr[1000006];
vector<int> vct[1000006];
vector<int> mp(1000006,0);
vector<bool> vis(1000006,false);
int last[1000006]; //上一个当前数字出现的位置.
int nex[1000006]; //下一个出现k次当数字的位置.
int lmx[1000006]; //左边第一个大于当前数字的位置.
int rmx[1000006]; //右边第一个大于当前数字的位置.
//不懂不懂..没思路...一开始想着很混乱,最大值是不同数字,又是隔开的,又是区间的,还要满足k个..晕..
//key:这个时候就要考虑,需要什么信息?可以预处理出来吗?
//①也不难..可以"预处理"之后,o(1)知道每个数字左边和右边第一个比它大的位置.
//②也可以o(1)知道每个数字从此位置起,往右直至其出现k次的位置在哪里.
//③还可以维护每个数字,上一次出现的位置.
//有了以上三个信息,可以枚举"每个位置作为第一个最大值"时,可以得到的贡献.
//即合法的左区间为(max(lmx,last),i],合法的右区间为[nex,rmx). last为上一个当前数字的位置,nex第k次出现当前数字的位置.
key:其实以前做过类似的题,应该是st表写的.也是只考虑每个点,对全部右区间的贡献,而对于左区间,只考虑到上一个当前数字为止.
这样就不会算重算漏.
//顾影自怜--这题官方题解是有问题的..
//https://codeforces.com/group/L9GOcnr1dm/contest/564037/attachments/download/28062/statements.pdf
void solve(){ //G
cin>>n>>k;
for(int i=1;i<=n+2;i++) vct[i].clear(),mp[i]=0,vis[i]=false,last[i]=0,nex[i]=0,lmx[i]=0,rmx[i]=0;
for(int i=1;i<=n;i++) {
cin>>arr[i];
last[i]=mp[arr[i]];
mp[arr[i]]=i;
vct[arr[i]].emplace_back(i); //可知第k个arr[i]的位置.
}
if(k==1){} //最多的情况是(n+(1+n))/2,爆int...一开始没开longlong,怕MLE.然后wa2了,但是实际上完全不会MLE..也不用特判.
stack<int> stk; //单调栈.
for(int i=1;i<=n;i++){
while(!stk.empty()&&arr[i]>=arr[stk.top()]) stk.pop();
if(!stk.empty()) lmx[i]=stk.top();
stk.emplace(i); //这里不用判条件了,直接入栈
}
while(!stk.empty()) stk.pop();
for(int i=n;i>=1;i--){
while(!stk.empty()&&arr[i]>=arr[stk.top()]) stk.pop();
if(!stk.empty()) rmx[i]=stk.top();
else rmx[i]=n+1;
stk.emplace(i); //这里不用判条件了,直接入栈
}
for(int i=1;i<=n;i++){
if(vis[arr[i]]) continue;
vis[arr[i]]=true;
for(int j=0;j+k-1<(int)vct[arr[i]].size();j++){
nex[vct[arr[i]][j]]=vct[arr[i]][j+k-1];
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!nex[i]||nex[i]>rmx[i]) continue;
int l=max(lmx[i],last[i])+1;
int r=rmx[i]-1;
ans+=(i-l+1)*(r-nex[i]+1);
}
cout<<ans<<endl;
}