CF每日5题Day4（1400）

好困，感觉很累，今天想赶紧写完题早睡。睡眠不足感觉做题都慢了。

1- 1761C 构造

void solve(){int n;cin>>n;vector<vector<int>>a(n+1);forr(i,1,n){//保证每个集合不同a[i].push_back(i);}forr(i,1,n){string s;cin>>s;forr(j,1,n){if(s[j-1]=='1')a[j].push_back(i);//i是j的子集 j有的i没有}}forr(i,1,n){cout<<a[i].size()<<' ';for(auto ans:a[i]){cout<<ans<<' ';}cout<<endl;}
}

2- 1735C 贪心 模拟

成环问题

题意

• string s是需要加密的，string t是加密过后的
• 给string t，找加密前词性最小的string s
• 字母圆圈的排列可以不按字母表，但是必须包含26个字母
• string s每个字母 对应在字母表中 出现最早 就是字典序小
• 总结就是找一个字母圈的映射顺序，让string s最小

代码

数据量不大 可以每次链接的时候判断是否成合法的环

map<char,char>pre;//记录t中对s的映射关系 如果pre[i]=j 那么i from t->j from s
map<char,int>vis;//记录要映射的这个字母有没有用过
int check(char a,char b){//判断 如果a->b形成的环是否合法//从a指向b a的映射是b a->bint now=(int)b,i=1;map<int,int>tp;tp[(int)a]=1;//假设已经从a遍历过来到b了while (now!=-1){// cout<<(char)(now)<<pre.count(now)<<endl;if(!pre.count(now))return false;//环断了 还没形成完整的环now=(int)pre[(char)now];i++;if(tp[now]){//成了环now=-1;break;}}if(now==-1&&i<26)return true;else return false;
}
void ans(char x){forr(i,0,25){char c='a'+i;if(c==x||vis[c])continue;if(!check(x,c)){//判断链接x和c是否会成不合法的环//勇敢链接pre[x]=c;vis[c]=1;break;}}
}
void solve(){pre.clear();vis.clear();int n;string t;cin>>n>>t;int fg=0;forr(i,0,n-1){if(!pre.count(t[i])){ans(t[i]);}}for(auto c:t){cout<<pre[c];}cout<<endl;
}

3- 1609C 贪心

• 总乘积是质数 那肯定是$1\times prime$的组合
• 先确定质数的位置 然后再前后跳找$\times 1$的位置 确定范围 也就确定了$(i,k)$
• 一开始想的是先确定1的位置 但是发现可能会出现都是1的乘积，这样不是质数但是增加了运算量

bool is_prime(int n){if(n==1)return false;for(int i=2;i*i<=n;i++)if(n%i==0)return false;return true;
}
void solve(){int n,e;cin>>n>>e;vector<int>a(n+1);vector<int>ps;int ans=0;forr(i,1,n){cin>>a[i];if(is_prime(a[i]))ps.push_back(i);//先找素数}for(auto x:ps){int idx=0,mul=1;int fr=(x-1)/e,ba=(n-x)/e;int f1=0,b1=0;forr(k,1,fr){//向前跳idx=x-k*e;if(a[idx]==1)f1++;else break;//跳到不是1的a[i] 再乘它就不是素数了 跳出循环防止tle}forr(k,1,ba){//向后找if(k==0)continue;idx=x+k*e;if(a[idx]==1)b1++;else break;}ans+=((b1+1)*f1+b1);}cout<<ans<<endl;
}

4- 988C 模拟 map

使用map优化查找效率

struct ans{int x,y;
};
void solve(){int k;cin>>k;vector<int>s(k+1);map<int,int>m[k+1];map<int,ans>sum;forr(i,1,k){int n;cin>>n;forr(j,1,n){int aa;cin>>aa;s[i]+=aa;if(!m[i].count(aa))m[i][aa]=j;//记录每一种数的位置}}forr(i,1,k){for(auto j:m[i]){int now=s[i]-j.first;int nx=i,ny=j.second;if(sum.count(now)){cout<<"YES"<<endl;cout<<sum[now].x<<' '<<sum[now].y<<endl;cout<<nx<<' '<<ny<<endl;return;}else{sum[now]={nx,ny};}}}cout<<"NO"<<endl;
}

5- 1131B 思维

• 平局 就是找前后两场比赛共同的区间大小
• 记录上次平局 就是$min(x,y)$ 这次仍然是这个平局 去重

void solve(){int n;cin>>n;int px=0,py=0;int x,y;int ans=0,lst=-1;forr(i,1,n){cin>>x>>y;if(min(x,y)>=max(px,py))ans+=min(x,y)-max(px,py)+1;if(max(px,py)==lst)ans--;lst=min(x,y);px=x,py=y;}cout<<ans<<endl;
}