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(){ //Agetline(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(){ //Jcin>>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(){ //Ccin>>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(){ //Eint 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(){ //Gcin>>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;
}
