果然是被生活压垮的人，即将退役和告别大学生活了
早上放下了GRE来看题，写了两个小时就又不得不去学gre了，希望330+
比赛开始20分钟之后才到自习室，然后这个时候排名已经1100开外了
第一题，一看，问最长的等差数列长度，给了公差，所以拿map记录一下就好了
#include <bits/stdc++.h>
using namespace std;
#define limit (2000000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
#define debug(x) cout<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline ll read(){
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;char s = getchar();
while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + s - '0';s = getchar();}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if(x/ 10) print(x / 10);
*O++=x % 10+'0';
}
void write(ll x, char c = 't') {
if(x < 0)putchar('-'),x = -x;
print(x);
if(!isalpha(c))*O++ = c;
fwrite(obuf,O-obuf,1,stdout);
O = obuf;
}
int kase;
int n, m,k;
int a[limit];
void solve(){
cin>>n>>k;
map<int, int>mp;
rep(i,1,n){
cin>>a[i];
}
sort(a + 1, a + 1 + n);
ll ans = 1;
rep(i,1,n){
if(!mp.count(a[i])){
mp[a[i]] = mp[a[i] - k] + 1;
ans = max(ans, 1ll * mp[a[i]]);
}
}
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
//FOUT;
#endif
//FASTIO
//kase = read();
//while (kase--)
solve();
cerr << "Time elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
然后看了下K，问最大匹配，数据还小得一批，笑了，暴力加边，dinic水了过去
#include <bits/stdc++.h>
using namespace std;
#define limit (200000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
#define debug(x) cout<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline ll read(){
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;char s = getchar();
while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + s - '0';s = getchar();}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if(x/ 10) print(x / 10);
*O++=x % 10+'0';
}
void write(ll x, char c = 't') {
if(x < 0)putchar('-'),x = -x;
print(x);
if(!isalpha(c))*O++ = c;
fwrite(obuf,O-obuf,1,stdout);
O = obuf;
}
int kase;
int n,m,vs,ve,p;
int layer[limit],head[limit], cnt;
struct node{
int to ,next;
ll flow, w;
}edge[limit];
ll max_flow;
void add_one(int u , int v, ll flow = 0){
edge[cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].flow = flow;
edge[cnt].w = 0;
head[u] = cnt++;
}
inline void add(int u, int v, ll flow){
add_one(u,v,flow);
add_one(v, u,0);
}
inline void init(bool flag = true){
if(flag){
memset(head, -1, sizeof(head));
cnt = 0;
}else{
memset(layer, -1, sizeof(layer));
}
}
inline bool bfs(){
init(false);
queue<int>q;
layer[vs] = 0;//从第0层开始
q.push(vs);
while (q.size()){
int u = q.front();
q.pop();
traverse(u){
int v = edge[i].to,flow = edge[i].flow;
if(layer[v] == -1 && flow > 0){
layer[v] = layer[u] + 1;//迭代加深
q.push(v);
}
}
}
return ~layer[ve];
}
ll dfs(int u, ll flow){
if(u == ve)return flow;
ll rev_flow = 0,min_flow;
traverse(u){
int v =edge[i].to;
ll t_flow = edge[i].flow;
if(layer[v] == layer[u] + 1 && t_flow > 0){
min_flow = dfs(v, min(flow, t_flow));
flow -= min_flow;
edge[i].flow -= min_flow;
rev_flow += min_flow;
edge[i^1].flow += min_flow;
if(!flow)break;
}
}
if(!rev_flow)layer[u] = -1;
return rev_flow;
}
void dinic(){
while (bfs()){
max_flow += dfs(vs,inf);
}
}
int a[limit], b[limit];
void solve(){
init();
n = read();
vs = 90001, ve = vs + 1;
rep(i,1,n){
a[i] = read();
add(vs, i, 1);
}
rep(i,1,n){
b[i] = read();
add(i + n, ve, 1);
}
rep(i,1,n){
rep(j,1,n){
if(__gcd(a[i] , b[j]) != 1){
add(i, j + n, INF);
}
}
}
dinic();
write(max_flow);
}
int32_t main() {
#ifdef LOCAL
FOPEN;
//FOUT;
#endif
//FASTIO
//kase = read();
//while (kase--)
solve();
cerr << "Time elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
然后C题，问匹配，好像列出来之后只有6种情况能对答案产生贡献，那么就手动模拟一下就好了
#include <bits/stdc++.h>
using namespace std;
#define limit (2000000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
#define debug(x) cout<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline ll read(){
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;char s = getchar();
while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + s - '0';s = getchar();}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if(x/ 10) print(x / 10);
*O++=x % 10+'0';
}
void write(ll x, char c = 't') {
if(x < 0)putchar('-'),x = -x;
print(x);
if(!isalpha(c))*O++ = c;
fwrite(obuf,O-obuf,1,stdout);
O = obuf;
}
int kase;
int n,m,k;
int ca,cat,c,at,t,a;
void solve(){
cin>>n;
rep(i,1,n) {
string str;
cin >> str;
if (str == "ca")++ca;
if (str == "cat")++cat;
if (str == "a")++a;
if (str == "at")++at;
if (str == "t")++t;
if (str == "c")++c;
}
// ca + t
ll ans = min(ca, t), tmp;
t -= ans, ca -= ans;
// c + at
tmp = min(c, at); ans += tmp;
c -= tmp, at -= tmp;
// cat
ans += cat, cat = 0;
// c + a + t
tmp = min({c , a , t}); ans += tmp;
c -= tmp, a -= tmp, t -= tmp;
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
//FOUT;
#endif
FASTIO
//kase = read();
//while (kase--)
solve();
cerr << "Time elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
然后看了看B，发现题意太过复杂，虽然感觉不难，但是念及自己可怜的分数还是算了，开了J
然后发现J的范围是1e7，很典型的素数筛题，想到根号分解数字，找到最小质因数，然后log计算贡献，再从增量里把这些剪掉就行，暴力加答案。
然后好家伙，tle了，我跟队友说不要写了，这题有坑，然后队友过了一会儿告诉我，tle个锤子，他过了。
然后我发现，好像__int128没关上，那没事了，果断提交并且AC，话说我这个__int128为了谨慎起见还开了fread，没想到这么毒瘤
#include <bits/stdc++.h>
using namespace std;
#define limit (20000000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
#define debug(x) cout<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline ll read(){
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;char s = getchar();
while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + s - '0';s = getchar();}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if(x/ 10) print(x / 10);
*O++=x % 10+'0';
}
void write(ll x, char c = 't') {
if(x < 0)putchar('-'),x = -x;
print(x);
if(!isalpha(c))*O++ = c;
fwrite(obuf,O-obuf,1,stdout);
O = obuf;
}
int kase;
ll n,m, k;
ll prime[limit], num[limit],tot;
int a[limit], b[limit];
void get_prime( const int &N=2e7){
memset(num, 1, sizeof(num));
tot = 0;
rep(i ,2,N){
if(num[i])prime[++tot] = i;
for(int j = 1 ; j <= tot && i * prime[j] <= N ; ++j){
num[i * prime[j]] = 0;
if(i % prime[j] == 0)break;//线性筛
}
}
}
void process(ll x){
if(num[x]){
a[x] = x;
b[x] = 1;
return;
}
for(ll i = 2 ; i * i <= x; ++i){
if(num[i] and x % i == 0){
a[x] = i;
ll tmp = x;
while(tmp % i == 0){
b[x]++;
tmp /= i;
}
return;
}
}
}
void solve(){
get_prime();
n = read(),m = read(), k= read();
rep(i,1 + k,n + k){
process(i);
}
ll ans = 0;
rep(i,1 + k,n + k){
ll ti = b[i] - (b[i] / m);
ll tmp = i;
rep(j,1,ti){
tmp /= a[i];
}
ans += i - tmp;
}
write(ans);
}
int32_t main() {
#ifdef LOCAL
FOPEN;
//FOUT;
#endif
FASTIO
//kase = read();
//while (kase--)
solve();
cerr << "Time elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
然后看了看I题，好像三分写假了，那就撤退好了，今天还有新的任务呢。
感觉之后还是多一些训练，希望有生之年能够成全我一次吧，今年ICPC加油！