Codeforces 898 贪心关闭最少闹钟 优先队列最少操作构造N/2squares 讨论情况哈希数字串分割a+b=c
2024-09-05 18:55:19
A
/* Huyyt */
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define pb push_back
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio();
cin.tie();
ll n;
cin >> n;
if(n%<=)
{
n-=n%;
}
else
{
n+=-n%;
}
cout<<n<<endl;
return ;
}
B
/* Huyyt */
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define pb push_back
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio();
cin.tie();
ll n;
cin >> n;
ll a,b;
cin >> a >> b;
ll bei=n/a;
ll now;
for(ll i=;i<=bei;i++)
{
now=n-i*a;
if(now%b==)
{
cout<<"YES"<<endl;
cout<<i<<" ";
cout<<now/b<<endl;
return ;
}
}
cout<<"NO"<<endl;
return ;
}
C
/* Huyyt */
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define pb push_back
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
using namespace std;
typedef long long ll;
map<int, string> mpb;
map<string, int> mp;
string p[][];
int ok[][];
int num[];
int ans[];
int pop = ;
bool check(string a, string b)
{
if (b.size() > a.size())
{
return false;
}
for (int i = ; i < b.size(); i++)
{
if (a[a.size() - i - ] != b[b.size() - i - ])
{
return false;
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int flag;
int n;
cin >> n;
int now;
string ch;
string ch2;
for (int i = ; i <= n; i++)
{
cin >> ch >> now;
if (!mp[ch])
{
mp[ch] = ++pop;
mpb[pop] = ch;
}
for (int j = ; j <= now; j++)
{
cin >> ch2;
flag=;
for(int k=;k<=num[mp[ch]];k++)
{
if(ch2==p[mp[ch]][k])
{
flag=;
break;
}
}
if(flag)
p[mp[ch]][++num[mp[ch]]] = ch2;
}
}
for (int i = ; i <= pop; i++)
{
ans[i] = num[i];
//cout<<ans[i]<<endl;
for (int j = ; j <= num[i]; j++)
{
for (int k = ; k <= num[i]; k++)
{
if (j == k)
{
continue;
}
if (check(p[i][k], p[i][j]))
{
ok[i][j] = ;
ans[i]--;
break;
}
}
}
}
cout << pop << endl;
for (int i = ; i <= pop; i++)
{
cout << mpb[i] << " ";
cout << ans[i] << " ";
for (int j = ; j <= num[i]; j++)
{
if (!ok[i][j])
{
cout << p[i][j] << " ";
}
}
cout << endl;
}
return ;
}
D
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll LLmaxn = 2e18;
const int N = 1e6 + ;
int num[N];
int visit[N];
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n, m, k;
cin >> n >> m >> k;
for (int i = ; i <= n; i++)
{
cin >> num[i];
visit[num[i]] = ;
}
int anser = ;
int now = ;
for (int i = ; i <= ; i++)
{
if (!visit[i])
{
if ((i - m + >= ) && visit[i - m + ])
{
now--;
}
continue;
}
if (now < k - )
{
now++;
}
else
{
visit[i] = ;
//cout << i << endl;
anser++;
}
if ((i - m + >= ) && visit[i - m + ])
{
now--;
}
}
cout << anser << endl;
return ;
}
E
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll LLmaxn = 2e18;
const int N = 2e5 + ;
ll num[N];
ll cha[N];
priority_queue<ll, vector<ll>, greater<ll> >q;
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n;
cin >> n;
int sum = ;
int zero = ;
for (int i = ; i <= n; i++)
{
cin >> num[i];
ll s = sqrt(num[i]);
cha[i] = min(abs(s * s - num[i]), (s + ) * (s + ) - num[i]);
if (cha[i] == )
{
sum++;
}
else
{
q.push(cha[i]);
}
if (num[i] == )
{
zero++;
}
}
if (sum >= n / )
{
if (sum == n / )
{
cout << << endl;
return ;
}
if (zero <= n / )
{
cout << sum - n / << endl;
}
else
{
cout << sum - zero + (zero - n / ) * << endl;
}
return ;
}
int t = n / - sum;
ll anser = ;
while (t--)
{
anser += q.top();
q.pop();
}
cout << anser << endl;
return ;
}
F
题意为给你一个长度不超过1e6的数字串 要求你插入'+'和'='使得串被分为三个无前导零的数 a,b,c 且a+b=c
解:
分情况讨论 有且只有四种情况
①/② a.size/b.size=c.size ③/④ a.size/b.size=c.size-1 枚举的复杂度为n
每次直接用暴力来check的话 很明显check的复杂度是len 而len和n是一个级别的 总复杂度就是n2 不行
所以我们需要hash一下 先用hash判断 如果符合的话 再用字符串模拟大数check
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 1e6 + ;
const int sed = ;
const int mod = 1e9 + ;
int n;
char str[M]; //原数字串
int s[M]; //数字数组
int suf[M]; //
int bas[M]；
int inv[M];
long long pr(int a, int b) //快速幂
{
long long r = , base = a;
while (b != )
{
if (b & )
{
r = (r * base) % mod;
}
base = (base * base) % mod;
b >>= ;
}
return r;
}
bool check(int la, int lb, int lc)
{
int sava = la, savb = lb, savc = lc;
if (la > lc || lb > lc || la < || lb < || lc < )
{
return false;
}
int lia = , lib = la + , lic = la + lb + ;
if ((la > && s[lia] == ) || (lb > && s[lib] == ) || (lc > && s[lic] == ))
{
return false;
}
int ria = la, rib = la + lb, ric = la + lb + lc;
int vala, valb, valc, up = , tmp;
while (lc > )
{
if (la > )
{
vala = s[ria];
}
else
{
vala = ;
}
if (lb > )
{
valb = s[rib];
}
else
{
valb = ;
}
tmp = up + vala + valb;
up = tmp / ;
tmp %= ;
if (tmp != s[ric])
{
return false;
}
la--;
lb--;
lc--;
ria--;
rib--;
ric--;
}
if (up)
{
return false;
}
for (int i = ; i <= n; i++)
{
printf("%d", s[i]);
if (i == sava)
{
printf("+");
}
if (i == sava + savb)
{
printf("=");
}
}
return true;
}
int getval(int li, int ri)
{
int ret, tmp;
tmp = (0ll + suf[li] - suf[ri + ]) % mod;
tmp = (1ll * tmp * inv[n - ri]) % mod;
ret = (tmp % mod + mod) % mod;
return ret;
}
bool solve(int la, int lb, int lc)
{
int sava = la, savb = lb, savc = lc;
if (la > lc || lb > lc || la < || lb < || lc < )
{
return false;
}
int lia = , lib = la + , lic = la + lb + ;
if ((la > && s[lia] == ) || (lb > && s[lib] == ) || (lc > && s[lic] == ))
{
return false;
}
int ria = la, rib = la + lb, ric = la + lb + lc;
int vala, valb, valc;
vala = getval(lia, ria);
valb = getval(lib, rib);
valc = getval(lic, ric);
// cout<<la<<' '<<lb<<' '<<lc<<endl;
// cout<<vala<<' '<<valb<<' '<<valc%mod<<endl;
if ((0ll + vala + valb) % mod == valc % mod && check(la, lb, lc))
{
return true;
}
else
{
return false;
}
}
int main()
{
scanf("%s", str + );
n = strlen(str + );
for (int i = ; i <= n; i++)
{
s[i] = str[i] - '';
}
bas[] = ;
for (int i = ; i <= n; i++) //每一位的hash值
{
bas[i] = 1ll * bas[i - ] * sed % mod;
}
for (int i = ; i <= n; i++) //处理逆元
{
inv[i] = pr(bas[i], mod - );
}
suf[n + ] = ;
for (int i = n; i >= ; i--) //从后往前hash
{
suf[i] = (suf[i + ] + 1ll * bas[n - i] * s[i] % mod) % mod;
}
for (int i = ; i <= n; i++) //枚举
{
//四种情况 如果有的话就结束
//lc-1,lc-1,lc lc,lc,lc lc
if (solve(i - , n - i - (i - ), i) || solve(i, n - i - i, i) || solve(n - i - (i - ), i - , i) || solve(n - i - i, i, i))
{
return ;
}
}
return ;
}
最新文章
- C语言中内存的申请函数
- [linux]windows无法访问samba的安全性问题(关闭selinux)
- Linux里startup.sh 和 shutdown.sh
- Cobar-Client 实现策略总结
- Python开发【第一篇】Python模块中特殊变量
- bitmap缩放时抗锯齿
- Activity 状态的保存和恢复
- HDU 3362 Fix（状压dp）
- PAT (Advanced Level) 1027. Colors in Mars (20)
- UIView和layer的关系
- coursera_poj_魔兽世界终结版
- Eclipse多行同时进行编辑，可编辑或修改相同内容
- angular中$q.all用法
- linux服务器文件授权命令
- Selenium 3----窗口截图+关闭浏览器
- Spark架构与作业执行流程简介
- python 文件读写时用open还是codecs.open
- mysql 的REPLAYCE语句
- iOS图片按比例显示
- Ubuntu下Ruby的下载和编译源码安装