Codeforces_844
2024-09-05 19:48:25
A.统计字母个数。
#include<bits/stdc++.h>
using namespace std; string s;
int n;
map<char,int> mp; int main()
{
ios::sync_with_stdio();
cin >> s >> n;
int cnt = ;
for(int i = ;i < s.length();i++)
{
if(mp[s[i]] == ) cnt++;
mp[s[i]] = ;
}
if(s.length() < n) cout << "impossible" << endl;
else cout << max(,n-cnt) << endl;
return ;
}
B.统计每行每列0和1的个数,各自组合数计算数量,最后吧重复的n*m个减去。
#include<bits/stdc++.h>
using namespace std; int n,m,a[][]; long long c(int x)
{
long long ans = ;
for(int i = ;i <= x;i++) ans *= ;
return ans-;
} int main()
{
ios::sync_with_stdio();
cin >> n >>m;
for(int i = ;i <= n;i++)
{
for(int j = ;j <= m;j++) cin >> a[i][j];
}
long long ans = -n*m;
for(int i = ;i <= n;i++)
{
int cnt = ;
for(int j = ;j <= m;j++)
{
if(a[i][j] == ) cnt++;
}
ans += c(cnt);
ans += c(m-cnt);
}
for(int i = ;i <= m;i++)
{
int cnt = ;
for(int j = ;j <= n;j++)
{
if(a[j][i] == ) cnt++;
}
ans += c(cnt);
ans += c(n-cnt);
}
cout << ans << endl;
return ;
}
C.离散化后,统计环的数量。
#include<bits/stdc++.h>
using namespace std; int n,a[],b[],cnt,vis[] = {};
vector<int> v[],ans[];
map<int,int> mp; void dfs(int x)
{
vis[x] = ;
ans[cnt].push_back(x);
for(int i = ;i < v[x].size();i++)
{
int t = v[x][i];
if(vis[t]) continue;
dfs(t);
}
} int main()
{
ios::sync_with_stdio();
cin >> n;
for(int i = ;i <= n;i++) cin >> a[i],b[i] = a[i];
sort(b+,b++n);
for(int i = ;i <= n;i++) mp[b[i]] = i;
for(int i = ;i <= n;i++)
{
v[i].push_back(mp[a[i]]);
}
cnt = ;
for(int i = ;i <= n;i++)
{
if(!vis[i])
{
cnt++;
dfs(i);
}
}
cout << cnt << endl;
for(int i = ;i <= cnt;i++) sort(ans[i].begin(),ans[i].end());
for(int i = ;i <= cnt;i++)
{
cout << ans[i].size() << " ";
for(int j = ;j < ans[i].size();j++) cout << ans[i][j] << " ";
cout << endl;
}
return ;
}
D.随机1000个点,剩下线性找1000个,有连续1000个点不被随1000次随到的概率可以忽略。
#include<bits/stdc++.h>
using namespace std; int n,now,x;
map<int,int> mp; int main()
{
ios::sync_with_stdio();
srand(time());
cin >> n >> now >> x;
cout << "? " << now << endl;
int ne;
cin >> now >> ne;
if(now >= x)
{
cout << "! " << now << endl;
return ;
}
for(int i = ;i <= ;i++)
{
long long t = (long long)rand()*rand()%n+;
cout << "? " << t << endl;
int v,vv;
cin >> v >> vv;
if(v < x && v > now)
{
now = v;
ne = vv;
}
}
while(ne != -)
{
cout << "? " << ne << endl;
cin >> now >> ne;
if(now >= x)
{
cout << "! " << now << endl;
return ;
}
}
cout << "! -1" << endl;
return ;
}
最新文章
- Linux下Nodejs安装(完整详细)
- jQuery静态方法isFunction,isArray,isWindow,isNumeric使用和源码分析
- JS判断输入是否为整数的正则表达式
- 转载:混淆包含SlidingMenu、gson等Android代码的proguard写法
- 用户 &#39;sa&#39; 登录失败。 (Microsoft SQL Server,错误: 18456)
- ios获取远程json数据
- C#中经常使用的几种读取XML文件的方法
- 你知道现在有一种新的OCR技术叫“移动端车牌识别”吗?
- java web 中有效解决中文乱码问题-pageEncoding与charset区别, response和request的setCharacterEncoding 区别
- Angular2响应式表单
- 51Nod--1008
- susmote个人网站博客论坛(TexTec | 关注互联网技术,传播极客精神)
- Mybatis 基本使用
- 爬虫系列二(数据清洗--->;bs4解析数据)
- jQuery实现input框输入值动态搜索
- 2017-12-14python全栈9期第一天第二节之初始计算机系统
- Python新手入门英文词汇笔记(1-2)
- web自动化测试---css方式定位页面元素
- MSCRM中报表开发二:创建基于FetchXML报表
- bzoj4802 欧拉函数(附Millar-Rabin和Pollard-Rho讲解)