Educational Codeforces Round 14
2024-03-12 00:56:13
水
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// } int a[];
int main(){
int n;
cin>>n;
int k=;
for(int i=;i<n;i++){
cin>>a[i];
if(!a[i]) k++;
}
if(n==&&a[]==){
puts("NO");
exit();
}
if(n==&&a[]==){
puts("YES");
exit();
}
if(k==) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return ;
}
题意：判断是否是 ‘镜像‘
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
std::pair<char, char> mapP[] ={{'A', 'A'}, {'b', 'd'}, {'d', 'b'}, {'H', 'H'}, {'I', 'I'}, {'M', 'M'}, {'O', 'O'}, {'o', 'o'}, {'p', 'q'},
{'q', 'p'},{'T', 'T'}, {'U', 'U'}, {'V', 'V'}, {'v', 'v'},{'W', 'W'}, {'w', 'w'}, {'X', 'X'}, {'x', 'x'}, {'Y', 'Y'}
}; bool check(char a, char b){
for(std::pair<char, char> p : mapP){
if(p.first == a && p.second == b){
return true;
}
}
return false;
} int main(){
string s;
cin>>s;
int i,j;
bool flag=false;
for(i=,j=(int)s.length()-;i<=j;i++,j--){
if(!check(s[i],s[j])){
flag=;
puts("NIE");
break;
}
}
if(!flag)
puts("TAK");
return ;
}
题意：把一个值转换成 表达式a*10^b形式
字符处理
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// } int main(){
string s;
string str="";
int ansb;
cin>>s;
int p=;
while(p<(int)s.size()&&(s[p]==''||s[p]=='.')){
p++;
}
// cout<<p<<bndl;
str.push_back(s[p]);
str.push_back('.');
int pos=s.find('.');
if(pos==-) pos=s.size();
for(int i=++p;i<s.size();i++){
if(s[i]!='.') str.push_back(s[i]);
}
if(pos==p) ansb=;
else{
if(pos>p) ansb=pos-p;
else ansb=pos-p+;
}
while(str.back()==''||str.back()=='.') str.pop_back();
if(ansb) str+="E"+to_string(ansb);
printf("%s\n",str.c_str());
return ;
}
题意：n个数（1，2。。。n） m种操作：交换下标为x y的数， 每种操作可选任意次，输出最大字典序。
思路：并查集。最后把每个位置上同一个块的从大到小输出
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
int a[N];
int pre[N];
vector<int>ans[N];
vector<int>root;
int vis[N];
int pos[N];
int find(int x){
if(x==pre[x]) return x;
return pre[x]=find(pre[x]);
}
int main(){
std::ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=;i<=n;i++){
cin>>a[i];
pre[i]=i;
}
while(m--){
int x,y;
cin>>x>>y;
x=find(x),y=find(y);
if(x!=y) pre[x]=y;
}
for(int i=;i<=n;i++){
int x=find(i);
ans[x].push_back(a[i]);
if(!vis[x]){
root.push_back(x);
vis[x]=true;
}
}
for(int i=;i<(int)root.size();i++){ //从大到小排序
sort(ans[root[i]].rbegin(),ans[root[i]].rend());
}
for(int i=;i<n;i++){
cout<<ans[find(i)][pos[find(i)]++]<<" ";
}
cout<<ans[find(n)][pos[find(n)]]<<endl;
return ;
}
题意：n个数，选k个出来，形成一个新的序列，该序列相邻两个数异或后数的二进制中1的个数是3的倍数。问有几个序列
思路：每个数转化成一个点，两个数满足 异或后数的二进制1的个数是3倍数的则两点之间建一条边。转化成求边的条数。
矩阵快速幂
M(i,j)：(ai^aj)%3==0 则最后答案是M^(k-1)的元素和
借鉴了Q神的模板
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// } struct Matrix{
LL a[][];
Matrix(){
clc(a,);
}
void init(){
for(int i=;i<;i++) a[i][i]=;
}
Matrix operator * (const Matrix &B)const{
Matrix C;
for(int i=;i<;i++){
for(int k=;k<;k++){
for(int j=;j<;j++){
(C.a[i][j]+=a[i][k]*B.a[k][j])%=MOD;
}
}
}
return C;
}
Matrix operator ^ (const LL &t) const{
Matrix A= (*this),res;
res.init();
LL p=t;
while(p){
if(p&) res=res*A;
A=A*A;
p>>=;
}
return res;
}
};
LL a[];
int main(){
LL n,k;
scanf("%I64d%I64d",&n,&k);
for(int i=;i<n;i++){
scanf("%I64d",&a[i]);
}
Matrix A;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(__builtin_popcountll(a[i]^a[j])%==)
A.a[i][j]=;
}
}
LL ans=;
A=A^(k-);
for(int i=;i<n;i++){
for(int j=;j<n;j++){
(ans+=A.a[i][j])%=MOD;
}
}
printf("%I64d\n",ans);
return ;
}
题意：n个数，任选两个相乘，q次询问，每次输出不小于x的乘积对数
思路：总的方案数-小于x
预处理每种面积的方案数
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = *1e6+;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-); void fre() {
freopen("in.txt","r",stdin);
} // inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// } int cnt[N];
int maxn=*1e6;
LL a[N];
LL sum[N];
void init(){
for(int i=;i<=maxn;i++){
for(int j=;j*i<=maxn;j++){
if(i==j) a[i*j]+=(LL)cnt[i]*(cnt[i]-);
else a[i*j]+=(LL)cnt[i]*cnt[j];
}
}
for(int i=;i<=maxn;i++){
sum[i]=sum[i-]+a[i];
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=;i<n;i++){
int x;
scanf("%d",&x);
if(x<=maxn)
cnt[x]++;
}
init();
int q;
scanf("%d",&q);
while(q--){
int x;
scanf("%d",&x);
LL ans=(LL)n*(n-)-sum[x-];
printf("%I64d\n",ans);
}
return ;
}
最新文章
- nginx做nodejs（express等通用）反向代理
- RGB与HSV颜色空间
- CSS文档流
- 【JAVA】 @override报错的解决方法
- vector 内部方法大全 学习（初学者的参考资料）
- vagrant 设置除默认工项目之外的synced_folder一个坑
- c++拷贝构造函数(深拷贝，浅拷贝)详解
- HashSet的分析(转)
- TCP/IP的三次握手协议
- Ansible3：ansible.cfg配置说明【转】
- Ext Designer生成表格
- React Native调试实用技巧，React Native开发者必会的调试技巧
- cordova 开发
- JS 之 阻止事件冒泡，阻止默认事件，event.stopPropagation()和event.preventDefault()，return false的区别
- vue的技巧代码
- vue-cli+webpack项目，修改项目名称
- 机器学习实战 - python3 学习笔记（一） - k近邻算法
- 创建随机的9x9数独游戏终盘并打印
- ubuntu14.04 中virtual box 加入 usb
- Unity 网格 绘制