Codeforces Round #595 (Div. 3) A,B,C,D
2024-09-03 12:32:13
A题:n个学生，分成任意组，要求每组中任意两名学生的技能值相差不等于1，问最小分组.
#include<bits/stdc++.h> using namespace std; #define int long long
int arr[];
signed main(){
int _;
cin>>_;
while(_--){
int n;
cin>>n;
for(int i=;i<=n;i++)
cin>>arr[i];
sort(arr+,arr++n);
int sum=;
int flag=;
for(int i=;i<n;i++){
if(arr[i+]-arr[i]==){
flag=;
break;
}
}
if(flag){
printf("2\n");
}else{
printf("1\n");
}
}
return ;
}
/* */
B1题：
题意：n个学生，每个学生有单独的一本书，每天学生 i 会把 书给 ai，问每个学生重新拿到自己的书经过的天数。
思路：一发暴力水过
#include<bits/stdc++.h> using namespace std;
#define int long long
int arr[];
int ans[];
signed main(){
int _;
cin>>_;
while(_--){
int n;
cin>>n;
for(int i=;i<=n;i++)
scanf("%lld",&arr[i]);
for(int i=;i<=n;i++){
int sum=;
int temp=i;
while(){
sum++;
if(arr[temp]==i){
break;
}
temp=arr[temp];
}
ans[i]=sum;
}
for(int i=;i<=n;i++){
printf("%lld ",ans[i]);
}
printf("\n");
}
return ;
}
B2：
找环，只要在同一个环的天数相等。开始暴力。。。。。。。。。。。
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 200020
int arr[N];
int ans[N];
int vis[N];
int a[N];
signed main(){
int _;
cin>>_;
while(_--){
int n;
scanf("%lld",&n);
for(int i=;i<=n;i++){
scanf("%lld",&arr[i]);
vis[i]=;
} for(int i=;i<=n;i++){
int sum=;
if(vis[i])
continue;
int temp=i;
vector<int> v;
while(){
sum++;
if(arr[temp]==i){
break;
}
temp=arr[temp];
v.push_back(temp);
}
vis[i]=sum;
for(int j=;j<v.size();j++){
vis[v[j]]=sum;
}
// vis[i]=sum;
}
for(int i=;i<=n;i++){
printf("%lld ",vis[i]);
}
printf("\n");
}
return ;
}
/* 3 6
1 3 4 9 10
1 2 3 4 5
5 1 2 4 3
4 4 4 1 4
*/
C1:
题意：求大于n的m，m有不同的3的次幂。
想到进制，即可知道符合的数字3进制转换后只有1和0. 暴力一下。
#include<bits/stdc++.h> using namespace std;
#define int long long
int ans[]; signed main(){ int _;cin>>_;
while(_--){
int n;
scanf("%lld",&n);
if(n==){
cout<<""<<endl;continue;
}
if(n==){
cout<<<<endl;continue;
}
int i=n;
for(;;i++){
int temp=i;
int flag=;
while(temp){
int x=temp%;
if(x!=&&x!=){
flag=;
break;
}
temp/=;
}
if(flag){
cout<<i<<endl;
break;
}
}
}
return ;
}
C2:
思路：从左到右，找到第一个2的位置，然后开始模拟进位。第一个2后面的数全改为0。调了好久的BUG。
/*
10212121111
11000000000
110121212211
111000000000
11212211221
10000000000
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int fpow(int a,int b){
int res=;
while(b){
if(b%){
res*=a;
}
a*=a;
b/=;
}
return res;
}
signed main(){
int _;cin>>_;
while(_--){
int n;
cin>>n;
vector<int> v;
int temp;
temp=n;
while(temp){
v.push_back(temp%);
temp/=;
}
int flag1=-;
int flag2=;
int cnt=;
/*
for(int i=v.size()-1;i>=0;i--){ }
cout<<endl;
*/
for(int i=v.size()-;i>=;i--){
if(v[i]==){
flag1=i;
break;
}
if(v[i]==){
flag2=i;
}
}
if(flag1==-){
cout<<n<<endl;
continue;
}
if(!flag2){
int x=v.size();
cout<<fpow(,x)<<endl;
continue;
}else{
int ans[];
int cnt=;
for(int i=v.size()-;i>=;i--)
ans[i]=v[i];
int j;
for( j=flag1;j<v.size();j++){ if(ans[j]==){
ans[j]=;
ans[j+]=ans[j+]+;
}
}/*
for(int i=v.size()-1;i>=0;i--){
cout<<v[i]<<" ";
}
cout<<endl;
for(int i=0;i<j;i++){
cout<<ans[i]<<" ";
}
cout<<endl;*/
int X=;
// cout<<j<<" "<<endl;
for(int i=j-;;i--){
if(i<=flag1){
break;
}
if(ans[i])
X+=fpow(,i);
// cout<<fpow(3,i)<<" ";
}
cout<<X<<endl;
}
}
return ;
}
【补题...................................】
D1，D2题：
题意：给出n个线段，要求同一个点不能有超过k条线段覆盖。求最少要删多少条线段。
思路：r从小到大排序。r相等的时候l从小到大排序。然后进行区间的最值和区间修改。用线段树维护。
然后在网上找了一个板子 套了一下。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional> #define l(x) t[x].l
#define r(x) t[x].r
#define dat(x) t[x].dat
#define sum(x) t[x].sum
#define add(x) t[x].add
#define clean(x, y) memset(x, y, sizeof(x))
const int maxn = 1e5 + ;
const int inf = 0x3f3f3f3f;
typedef long long LL;
using namespace std; template <typename T>
inline void read(T &s) {
s = ;
T w = , ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
s *= w;
} template<typename T>
inline void write(T s) {
if (s < ) putchar('-'), s = -s;
if (s > ) write(s / );
putchar(s % + '');
} int n;
int a[maxn];
struct tree {
int l, r;
LL dat, sum, add;
} t[maxn << ]; void build(int p, int l, int r) {
l(p) = l, r(p) = r;
if (l == r) { sum(p) = a[l]; return ; }
int mid = (l + r) >> ;
build(p << , l, mid);
build(p << | , mid + , r);
dat(p) = dat(p << ) + dat(p << | );
// sum(p) = sum(p << 1) + sum(p << 1 | 1);
} void spread(int p) {
if (add(p)) {
// sum(p << 1) = add(p) * (r(p << 1) - l(p << 1) + 1);
// sum(p << 1 | 1) = add(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
add(p << ) += add(p);
add(p << | ) += add(p);
dat(p << ) += add(p);
dat(p << | ) += add(p);
add(p) = ;
}
} void change(int p, int l, int r, int d) {
if (l <= l(p) && r >= r(p)) {
sum(p) += (LL) d * (r(p) - l(p) + );
add(p) += d;
dat(p) += d;
return ;
}
spread(p);
int mid = (l(p) + r(p)) >> ;
if (l <= mid) change(p << , l, r, d);
if (r > mid) change(p << | , l, r, d);
sum(p) = sum(p << ) + sum(p << | );
dat(p) = max(dat(p << ), dat(p << | ));
} LL ask(int p, int l, int r) {
if (l <= l(p) && r >= r(p)) return dat(p);
spread(p);
int mid = (l(p) + r(p)) >> ;
LL val = ;
if (l <= mid) val = max(val, ask(p << , l, r));
if (r > mid) val = max(val, ask(p << | , l, r));
return val;
} int main() {
read(n);
build(, , n);
for (int i = ; i <= n; ++i) {
int opt, x, y;
read(opt), read(x), read(y);
if (opt == )
change(, x, y, );
else{
int T=ask(, x, y);
write(T); putchar('\n');
}
}
return ;
}
E题待补。
最新文章
- oracle临时表空间操作
- 微软2017校招笔试题3 registration day
- SQLSERVER 数据库性能的基本
- java web环境配置类型问题
- 【转】PHP网站常见安全漏洞，及相应防范措施总结
- UVA 10763 Foreign Exchange
- oracle死锁模拟
- 有关va_list和vsnprintf输出函数的问题
- String to Integer (atoi) leetcode
- leetcode — partition-list
- Spring @Qualifier
- Windows批量修改文件夹及子文件夹下文件的扩展名
- CentOS 7.X 关闭SELinux
- Asp.net Vnext 调试源码
- ExampleConfigurationSectionHandler
- tensorflow训练线性回归模型
- 【Django】Django迁移数据库
- mysql 索引 大于等于 走不走索引 最左前缀
- 特殊用途语言特性(默认实参/内联函数/constexpr函数/assert预处理宏/NDEBUG预处理变量)
- Spring MVC集成Log4j