SMU WINTER 4th
总
补题有收获的是
训4 f 训5 d的代码细节实现 f 训6 a
pta 训1 12 训2 7
天梯没完全补完，假期再补补
补题
牛客
训4
https://ac.nowcoder.com/acm/contest/120564#question
A
双重循环判断有多少个数小于等于ai
if (cnt * 10 >= (n - 1) * 8) sum += a[i];
B
用前缀和记录第i个首领在位第1年是公元几年
然后每次询问时b[x]+y-1
I
手动模拟会发现 多种颜色筹码下注会使得期望4进一步降低
于是所有筹码都不下注是最优解
输出"####"即可
C
构造的序列最后就是格雷码
格雷码：相邻两个数字在二进制中有且仅有一位不同
H
维护受单点更新影响的少量状态，也就是说维护的是每个格子作为中心时、曼哈顿距离不超过2的13个格子的总和
预先计算每个格子f[i][j]（以该格子为中心、曼哈顿距离≤2 的菱形区域之和），当某个格点(x,y)增加z时，仅会影响满足∣i−x∣+∣j−y∣≤2 的至多13个中心格子的f值，逐个把这13个f加上z并更新全局最大值即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=998244353;
const ll N=5e2+10;
ll a[N][N];
ll f[N][N];
ll cnt;
ll ddx[15],ddy[15];
void solve()
{
ll n,m,q;cin>>n>>m>>q;
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
cin>>a[i][j];
}
}
for(ll i=-2;i<=2;++i){
for(ll j=-2;j<=2;++j){
if(abs(i)+abs(j)<=2){
ddx[cnt]=i;
ddy[cnt]=j;
cnt++;
}
}
}
ll maxval=-1;
ll maxi=1,maxj=1;
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
ll sum=0;
for(ll k=0;k<cnt;++k){
ll xx=i+ddx[k];
ll yy=j+ddy[k];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
sum+=a[xx][yy];
}
}
f[i][j]=sum;
if(sum>maxval){
maxval=sum;
maxi=i;
maxj=j;
}
}
}
for(ll i=0;i<q;++i){
ll x,y,z;cin>>x>>y>>z;
a[x][y]+=z;
for(ll i=0;i<cnt;++i){
ll xx=x+ddx[i];
ll yy=y+ddy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
f[xx][yy]+=z;
if(f[xx][yy]>maxval){
maxval=f[xx][yy];
maxi=xx;
maxj=yy;
}
}
}
cout<<maxi<<" "<<maxj<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
// cin>>lll;
while(lll--)
{
solve();
// if(lll) cout<<'\n';
}
return 0;
}
F
最后的权值=是mex为2的子串数量×2+全0子串数量
mex为2的子串数量+全0子串数量+全1子串数量=所有子串数量
显然全1子串没有贡献，所以需要最小化全1字串的数量
若1多0少，先把1铺好，把1平均分成a+1块，在块与块之间插入0
若0多1少，把所有的1分开填在0的中间
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=998244353;
const ll N=5e2+10;
ll a[N][N];
ll f[N][N];
ll cnt;
ll ddx[15],ddy[15];
void solve()
{
int a,b;cin>>a>>b;
if(a==0){
for(int i=1;i<=b;i++){
cout<<1;
}
return ;
}
if(b==0){
for(int i=1;i<=a;i++){
cout<<0;
}
return ;
}
string s="";
if(a<b){
int x=b/(a+1),y=b%(a+1);
for(int i=1;i<=a;i++){
int len=x;
if(i-1<y){
len+=1;
}
string temp(len,'1');
s+=temp;
s+='0';
}
int sum=b-x*a-min(y,a);
string tmp(sum,'1');
// cout<<tmp<<'\n';
s+=tmp;
}else if(a>=b){
int x=a/(b+1),y=a%(b+1);
for(int i=1;i<=b;i++){
int len=x;
if(i-1<y){
len+=1;
}
string temp(len,'0');
s+=temp;
s+='1';
}
int sum=a-x*b-min(y,b);
string tmp(sum,'0');
s+=tmp;
}
cout<<s;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
cin>>lll;
while(lll--)
{
solve();
if(lll) cout<<'\n';
}
return 0;
}
训5
https://ac.nowcoder.com/acm/contest/120565#question
B
偶数行输出/\，奇数行输出\/
注意转义字符
J
赛时做法行列对角线求值，去对比的
G
用代码模拟了遍
按着这个写就行了
但是搞不懂的是我用c++交，直接输出答案不行
换成php同样的答案就过了
这样wa了一发
D
读完题 猜测发现和哈夫曼树很像
后面查了这类题叫哈夫曼编码（最优合并）问题
实现的一些细节写在代码里面了
用的是map写的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=1e9+7;
const ll N=1e5+10;
//ll a[N][N];
//ll f[N][N];
void solve()
{
ll n;cin>>n;
map<ll,ll>mp;//<堆重量，该重量的堆的数量>
ll tot=0;//总堆数
for(ll i=0;i<n;++i){
ll c,w;cin>>c>>w;
mp[w]+=c;
tot+=c;
}
bool f=false;//当前是否手里暂存着一个尚未合并的单独堆
ll cw=0;
ll ans=0;
while(tot>=2){
if(f){//有剩余的单个堆，需要和当前最小堆合并
auto it=mp.begin();
ll w=it->first;
ll k=it->second;
ll cost=cw+w;//合并代价
ans=(ans+cost)%modd;
ll nw=cw+w;//合并后新堆重量
f=false;//剩余堆已合并，重置标记
tot--;
if(k==1){
mp.erase(it);
}else{
it->second=k-1;
}
mp[nw]++;
}else{
if(mp.empty()) break;
auto it=mp.begin();
ll w=it->first;
ll k=it->second;
if(k>=2){//数量>=2,可批量合并
ll t=k/2;
ll cost=(2*w%modd)*(t%modd)%modd;//记得modd
ans=(ans+cost)%modd;
ll nw=2*w;
tot-=t;
if(k%2==0){
mp.erase(it);
}else{
f=true;
cw=w;
mp.erase(it);
}
mp[nw]+=t;
}else{//数量为1，无法批量合并，标记为单个堆
f=true;
cw=w;
mp.erase(it);
}
}
}
cout<<ans%modd;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
// cin>>lll;
while(lll--)
{
solve();
// if(lll) cout<<'\n';
}
return 0;
}
F
赛时写到后面看糊涂了有点
先贪心求得基础解：先算全填td（n/2b）或全填qcjjkkt（n/7a）的最大值；
然后枚举补漏：0~10 次小范围枚举 4 种混合组合（单决策+8 长度组合/8长度组合+单决策），覆盖56（2、7、8 最小公倍数）内剩余长度的最优解
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve()
{
ll n,a,b;
cin >> n >> a >> b;
ll ans = max(n/2*b,n/7*a); //纯贪心的两个基础解
for(ll i = 0;i <= 10; ++i){
//先放i个td，剩下全放qcjjkktd
if( i*2 <= n )ans = max(ans,b*i+(n-2*i)/8*(a+b));
//先放i个qcjjkkt(7长度)，剩下的全放qcjjkktd(8长度)
if( i*7 <= n )ans = max(ans,a*i+(n-7*i)/8*(a+b));
//先放i个qcjjkktd(8长度)，剩下的全放qcjjkkt(7长度)
if( i*8 <= n )ans = max(ans,i*(a+b)+(n-8*i)/7*a);
//先放i个qcjjkktd(8长度)，剩下的全放td(2长度)
if( i*8 <= n )ans = max(ans,i*(a+b)+(n-8*i)/2*b);
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
cin>>lll;
while(lll--)
{
solve();
}
return 0;
}
训6
A
每次选择打磨1单位能让斜边减少最多的边。用大顶堆维护每把尺子当前打磨1单位的边际收益（sqrt(x方+k方)-sqrt(x方+(k-1)方)），每次取出堆顶（最大收益）执行打磨，更新剩余长度后重新计算收益入堆（若仍可打磨），直到用完打磨额度w或无可用边
比赛的时候没调试完。。。。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=2048;
bool dp[N+10][N]={false};
vector<ll>gp;
struct node{
double g;
double sq;
ll a;ll idx;
bool operator<(const node& t) const{
return g<t.g;
}
};
void solve()
{
ll n,w;cin>>n>>w;
double tot=0.0;
priority_queue<node>pq;
for(ll i=0;i<n;++i){
ll x,y;cin>>x>>y;
double sq=(double)x*x;
double cur=sqrt(sq+(double)y*y);
tot+=cur;
if(y>0){
double nxt=sqrt(sq+(double)(y-1)*(y-1));
double gain=cur-nxt;
pq.push({gain,sq,y,i});
}
}
for(ll i=0;i<w;++i){
if(pq.empty()) break;
node top=pq.top();
pq.pop();
tot-=top.g;
ll nw=top.a-1;
if(nw>0){
double cur=sqrt(top.sq+(double)nw*nw);
double nxt=sqrt(top.sq+(double)(nw-1)*(nw-1));
double gain=cur-nxt;
pq.push({gain,top.sq,nw,top.idx});
}
}
cout<<fixed<<setprecision(10)<<tot;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
// cin>>lll;
while(lll--)
{
solve();
}
return 0;
}
pta
天梯赛题目看得头晕
看到了去年做过的些题 有些还在想为什么这个题去年不会做
天梯训1
7-12 智能护理中心统计
- 将管理结点（字符串）、老人（数字）映射为唯一数字ID
- 用数组构建管理结点的父子层级关系，同时记录各结点直接管辖的老人数、每位老人当前归属的结点
- 查询指令通过 DFS 遍历目标结点子树，累加所有结点的老人数；转移指令直接更新老人原/新归属结点的计数及老人归属记录，实现动态维护；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int maxn = 2e5 + 5;
int indx = 1;
map<string, int> mp;
int N, M;
int peo[maxn]; // 编号为i的管理节点的老人数量
vector<int> G[maxn];
int fa[maxn]; // 老人所在的管理节点
// 获取字符串对应的数字标识
int get(string s) {
if (mp[s]) {
return mp[s];
} else {
mp[s] = indx++;
return mp[s];
}
}
// 计算以pos为根的子树中老人的总数量
int dfs(int pos) {
int res = peo[pos];
for (auto u : G[pos]) {
res += dfs(u);
}
return res;
}
void solve()
{
cin >> N >> M;
while (M--) {
string a, b;
cin >> a >> b;
int x = get(a);
int y = get(b);
if (a[0] >= '0' && a[0] <= '9') {
peo[y]++;
fa[x] = y;
} else {
G[y].push_back(x);
}
}
char opt;
while (cin >> opt) {
if (opt == 'E') break;
string w, des;
if (opt == 'Q') {
// 查询
cin >> w;
int res = dfs(get(w));
cout << res << "\n";
} else if (opt == 'T') {
// 转移老人
cin >> w >> des;
int id = get(w);
int dd = get(des);
// 更新老人所在的管理节点的老人数量
peo[fa[id]]--; // 转出
fa[id] = dd; // 更新老人所在的管理节点
peo[dd]++; // 转入
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
// cin>>lll;
while(lll--)
{
solve();
}
return 0;
}
训2
7-7
写到这题的时候 看没啥人完整过，就先跳过了
后面反过来写，发现确实容易疏忽小点
要注意：
- 输入并不一定正常
- 可能会在第一次替换之后，恰好凑成了其他关键词
贴上实现代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
string str;
string s1="can you",s11="I can";
string s2="could you",s22="I could";
string s31="I",s32="me",s33="yoU";
int zm(char ch){
if(ch>='A'&&ch<='Z'||ch>='a'&&ch<='z') return 1;
return 0;
}
int main(){
int N;cin>>N;getchar();
for(int i=0;i<N;++i){
getline(cin,str);
cout<<str<<endl;
str=" "+str;
//大写转小写
for(int i=0;i<str.length();++i){
if(str[i]==' '&&!zm(str[i+1])&&!isdigit(str[i+1])){
str.erase(i,1);
i--;
}
if(str[i]>='A'&&str[i]<='Z'&&str[i]!='I') str[i]+=32;
if(str[i]=='?'){
str[i]='!';
}
}
//I换成you
for(int i=0;i<str.length();++i){
i=str.find(s31,i);
if(i==-1) break;
if(!(zm(str[i-1])||zm(str[i+s31.length()]))){
str.replace(i,s31.length(),s33);
}
}
//me换成you
for(int i=0;i<str.length();++i){
i=str.find(s32,i);
if(i==-1) break;
if(!(zm(str[i-1])||zm(str[i+s32.length()]))){
str.replace(i,s32.length(),s33);
}
}
//can you换成I can
for(int i=0;i<str.length();++i){
i=str.find(s1,i);
if(i==-1) break;
if(!(zm(str[i-1])||zm(str[i+s1.length()]))){
str.replace(i,s1.length(),s11);
}
}
//could you换成I could
for(int i=0;i<str.length();++i){
i=str.find(s2,i);
if(i==-1) break;
if(!(zm(str[i-1])||zm(str[i+s2.length()]))){
str.replace(i,s2.length(),s22);
}
}
for(int i=0;i<str.length();++i){
if(str[i]=='U') str[i]='u';
}
if(str[0]!=' ') str=" "+str;
cout<<"AI:"+str+"\n";
}
}
浙公网安备 33010602011771号