Codeforces 999
2024-09-03 10:53:09
A
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;
const int MAXQ = ;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v)
{
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}*/
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int num[];
int visit[];
int main()
{
int n, k;
read(n), read(k);
for (int i = ; i <= n; i++)
{
read(num[i]);
}
int anser = ;
for (int i = ; i <= n; i++)
{
if (num[i] <= k)
{
visit[i] = ;
anser++;
}
else
{
break;
}
}
for (int i = n; i >= ; i--)
{
if (visit[i])
{
break;
}
if (num[i] <= k)
{
anser++;
}
else
{
break;
}
}
cout << anser << endl;
return ;
}
B
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;
const int MAXQ = ;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v)
{
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}*/
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
string s;
void doit(int x)
{
for (int i = ; i <= x / - ; i++)
{
swap(s[i], s[x - - i]);
}
}
int main()
{
int n;
read(n);
cin >> s;
for (int i = ; i <= n; i++)
{
if (n % i == )
{
doit(i);
}
}
cout << s << endl;
return ;
}
C
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;
const int MAXQ = ;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v)
{
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}*/
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
string s;
int visit[];
queue<int> ch[];
int main()
{
int n, k;
read(n), read(k);
cin >> s;
for (int i = ; i < s.size(); i++)
{
ch[s[i] - 'a'].push(i);
//cout<<s[i]-'a'<<" "<<i<<endl;
}
for (int j = ; j <= k; j++)
{
for (int i = ; i <= ; i++)
{
if (ch[i].size() > )
{
visit[ch[i].front()] = ;
ch[i].pop();
break;
}
}
}
for (int i = ; i < s.size(); i++)
{
if(!visit[i])
{
cout<<s[i];
}
}
return ;
}
D
磨了半天 没想到直接暴力也能过
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = ;
int n, m, a[N];
vector<int> c[N];
LL ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++)
{
scanf("%d", &a[i]);
c[a[i] % m].push_back(i);
}
int ptr = ;
int goal = n / m;
for (int i = ; i < m; i++) //从0开始检查比goal大的
{
while ((int)c[i].size() > goal) //如果枚举到的比水平线高
{
ptr = max(ptr, i); //保证找到的要在其后
while ((int)c[ptr % m].size() >= goal) //找到小于水平线的
{
ptr ++;
}
int tk = min((int)c[i].size() - goal, goal - (int)c[ptr % m].size()); //取多出与缺少的最小值
int dlt = ptr - i; //多的和少的之间的距离
while (tk--)
{
ans += dlt;
a[c[i].back()] += dlt;
c[ptr % m].push_back(c[i].back());
c[i].pop_back();
}
}
}
printf("%lld\n", ans);
for (int i = ; i < n; i++)
{
printf("%d%c", a[i], " \n"[i + == n]);
}
}
E
暴力染色即可
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 5e3 + , MAXM = 5e3 + , N = 2e5 + ;
const int MAXQ = ;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;
inline void addedge(int u, int v)
{
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int du[MAXN], visit[MAXN];
int visit2[MAXN];
int ans = ;
void dfs(int x, int pre)
{
visit[x] = pre;
visit2[x] = ;
for (int i = Head[x]; i; i = nxt[i])
{
int v = to[i];
if (!visit2[v])
{
dfs(v, pre);
}
}
}
int vis[MAXN];
int main()
{
int n, m, s, u, v;
read(n), read(m), read(s);
for (int i = ; i <= m; i++)
{
read(u), read(v);
addedge(u, v);
du[v]++;
}
for (int i = ; i <= n; i++)
{
if (!visit[i])
{
mem(visit2, );
dfs(i, i);
}
}
mem(visit2,);
dfs(s, s);
for (int i = ; i <= n; i++)
{
if (vis[visit[i]] == )
{
vis[visit[i]] = ;
ans++;
}
}
cout << ans - << endl;
}
tarjan缩点后找入度为0的点 可以O(n+m)的做
F
dp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = ;
int n, k, c[N], f[N], h[N];
const int K = ;
int dp[ * K];
int cal(int x)
{
if (f[x] == )
{
return ;
}
int atmst = min(f[x] * k, c[x]);
for (int i = ; i <= atmst; i++)
{
dp[i] = ;
}
while (f[x]--)
{
for (int i = atmst; i >= ; i--)
for (int j = ; j <= k and i - j >= ; j++)
{
dp[i] = max(dp[i], dp[i - j] + h[j]);
}
}
return dp[atmst];
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = ; i < n * k; i++)
{
int ci;
scanf("%d", &ci);
c[ci]++;
}
for (int i = ; i < n; i++)
{
int fi;
scanf("%d", &fi);
f[fi]++;
}
for (int i = ; i <= k; i++)
{
scanf("%d", &h[i]);
}
int ans = ;
for (int i = ; i < N; i++)
{
ans += cal(i);
}
cout << ans << endl;
}
最新文章
- ASP.NET MVC 描述类型(一)
- [LeetCode] Wiggle Sort 摆动排序
- Linux File System Change Monitoring Technology、Notifier Technology
- git创建分支并提交项目
- Java：IO流之字符流缓冲区详解
- phpmyadmin 设置用户登录
- EL表达式中引用隐式变量
- 在C#中Color结构的各属性颜色对照表（转）
- 利用GUID唯一标识符并设置它的过期时间
- Python协程的引入与原理分析
- eclipse spring-boot-mybatis 的记录
- SWUST OJ(1028)
- Docker构建其它组件
- 在idea中设置记住git的用户名和密码
- 机器C盘临时区
- Linux软件包的安装（rpm+yum）
- svn up时提示跳过某节点
- python binascii模块详解
- Qt addStretch()详解
- hibernate -- 注解映射实体和表