GYM 两星级难度还是比较简单，随便写个题解吧。
http://codeforces.com/gym/101853
没啥好讲的的，离散化一下就随便写。
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define fi first
#define se second
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define ***(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
const int ME = 1e5 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> pii;
int n, m, q;
struct lp{
int opt,x,y;
}op[ME];
int vis[N],ar[N],br[N],now[N];
int main(){
int tim;
scanf("%d",&tim);
while(tim--){
scanf("%d%d", &n, &q);
mme(vis,0);int tot=0;
for(int i=1;i<=n;++i){
scanf("%d",&ar[i]);
br[tot++]=ar[i];
}
br[tot++]=0;
for(int i=0;i<q;++i){
int opt,x,y;
scanf("%d",&opt);
op[i].opt=opt;
if(opt==1){
scanf("%d%d",&x,&y);
op[i].x=x;op[i].y=y;
br[tot++]=y;
}
}
sort(br,br+tot);
int k = unique(br,br+tot)-br,sum=0;
for(int i=1;i<=n;++i){
now[i]=lower_bound(br,br+k,ar[i])-br+1;
if(now[i]==1)continue;
vis[now[i]]++;
if(vis[now[i]]==1)sum++;
}
for(int i=0;i<q;++i){
if(op[i].opt==2){
printf("%d\n", sum);
}else{
int x=op[i].x,y=op[i].y;
if(now[x]!=1){
vis[now[x]]--;
if(vis[now[x]]==0)sum--;
}
now[x]=lower_bound(br,br+k,y)-br+1;
if(now[x]!=1){
vis[now[x]]++;
if(vis[now[x]]==1)sum++;
}
}
}
}
return 0;
}
B - New Assignment
看一眼就知道是最大匹配，难的是建图。
有公共因子的男女可以配对，暴力 n^2logn,绝对超时。所以首先筛选所有的质因子，然后求每个数的所有的质因子，如果某个素数同时是两个数的质因子切这两个人性别不同就建边。然后求最大匹配，用n-最大匹配就是答案。
我的写法有点乱，看不懂留言。。。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=998244353;
const int maxn=1e6+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1);
struct edge {
int to,cap,rev;
};
vector <edge> G[maxn];
int level[maxn];
int iter[maxn];
void init(int _n) {
for(int i=0; i<=_n; i++) {
G[i].clear();
}
}
void bfs(int s) {
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty()) {
int v= que.front();
que.pop();
for(int i=0; i<G[v].size(); i++) {
edge & e=G[v][i];
if(e.cap>0&&level[e.to]<0) {
level[e.to]=level[v] + 1;
que.push(e.to);
}
}
}
}
void add(int from,int to,int cap) {
edge eg;
eg.to=to;
eg.cap=cap;
eg.rev=G[to].size();
G[from].push_back(eg);
eg.to=from;
eg.cap=0;
eg.rev=G[from].size()-1;
G[to].push_back(eg);
}
int dfs(int v,int t,int f) {
if(v == t)return f;
for(int &i = iter[v]; i < G[v].size(); i++) {
edge &e=G[v][i];
if(e.cap>0 && level[v]<level[e.to]) {
int d=dfs(e.to,t,min(f,e.cap));
if(d>0) {
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int maxflow(int s,int t) {
int flow=0;
for(;;) {
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f = dfs(s,t,INF))>0) {
flow +=f;
}
}
}
int a[maxn],b[maxn];
int prime[maxn];
vector<int> v;
void sieve(int _n) {
int tot=0;
memset(prime,0,sizeof(prime));
prime[0]=1;
prime[1]=1;
for(int i=2; i<=_n; i++) {
if (prime[i]==0) {
prime[i]=tot++; //是第几个素数
v.push_back(i);
for(int j=i*2; j<=_n; j+=i) {
prime[j]=1;
}
}
}
}
vector<int> k[maxn/10];
void df(int x,int pos) { //女的有某个质因子就把她加入质因子这个集合
if(x==1)return;
for(int i=0; i<v.size(); i++) {
if(x<v[i]) {
return ;
}
if(prime[x]!=1&&prime[x]!=x) {//优化，如果当前这个数是已经是质数就直接加进去
k[prime[x]].push_back(pos);
return ;
}
if(x%v[i]==0)k[i].push_back(pos);
while(x%v[i]==0) {
x/=v[i];
}
}
}
void df2(int x,int pos) { //男的如果有某个因子且这个质因子也是某个女的的质因子，就建边
if(x==1)return;
for(int i=0; i<v.size(); i++) {
if(x<v[i]) {
return ;
}
if(prime[x]!=1&&prime[x]!=x) {
i=prime[x];
for(int j=0; j<k[i].size(); j++) {
add(k[i][j],pos,1);
}
return ;
}
if(x%v[i]==0) {
for(int j=0; j<k[i].size(); j++) {
add(k[i][j],pos,1);
}
}
while(x%v[i]==0) {
x/=v[i];
}
}
}
int main() {
sieve(1e6+1);
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
for(int i=0; i<v.size(); i++) {
k[i].clear();
}
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
for(int i=1; i<=n; i++) {
char s[2];
scanf("%s",s);
if(s[0]=='F') {
b[i]=1;
} else b[i]=0;
}
init(n+1);
for(int i=1; i<=n; i++) {
if(b[i]==1) {
df(a[i],i);
}
}
for(int i=1; i<=n; i++) {
if(b[i]==0) {
df2(a[i],i);
}
}
for(int i=1; i<=n; i++) {
if(b[i]==1) {
add(0,i,1);
} else add(i,n+1,1);
}
printf("%d\n",n-maxflow(0,n+1));
}
return 0;
} C - Intersections
这个***题，看一眼求逆序对，然后队友告诉我可能点重合，特么没写，后来发现不用管点重合。。。。
以第一排为标号，求逆序对。//我用的是bit 数组求逆序对
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=998244353;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn];
ll bit[maxn+1],n;
int sum(int i) {
int s=0;
while(i>0) {
s +=bit[i];
i-=i&-i;
}
return s;
}
void add(int i,int x) {
while(i<=n) {
bit[i]+=x;
i+=i&-i;
}
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
memset(bit,0,sizeof(bit));
scanf("%d",&n);
for(int i=1; i<=n; i++) {
int x;
scanf("%d",&x);
a[x]=i;
}
ll ans=0;
for(int i=1; i<=n; i++) {
int x;
scanf("%d",&x);
ans+=i-1-sum(a[x]);
add(a[x],1);
}
cout<<ans<<endl;
}
return 0;
} D - Balloons
随便做
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define fi first
#define se second
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define ***(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = 1e6 + 7;
const int ME = 1e6 + 7;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
int n;
int ar[N];
int main(){
#ifndef ONLINE_JUDGE
#endif
int tim;
scanf("%d",&tim);
while(tim--){
scanf("%d",&n);
int tot=0;
for(int i=0;i<n;++i){
int x;
scanf("%d",&x);
if(x)tot++;
}
printf("%d\n", tot);
}
return 0;
} E - Maximum Sum
状压DP，如果看不出来多去刷一刷状压DP的题，和炮兵阵地很像，这题要注意预处理，不然会超时。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=998244353;
const int maxn=20;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int dp[20][1<<16];
vector<int> v[1<<16];
void init() {
for(int i=0; i<1<<16; i++) {
if((i&(i<<1))==0) {
for(int j=0; j<1<<16; j++) {
if((j&(j<<1))==0&&(j&(i<<1))==0&&(j&i)==0&&(j&(i>>1))==0) {
v[i].push_back(j);
}
}
}
}
}
int n;
int mp[maxn][maxn];
int tot[20][1<<16];
int main() {
int t;
init();
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
mem(tot,0);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%d",&mp[i][j]);
}
for(int j=0; j<v[0].size(); j++) {
int s=v[0][j],sum=0;
if(s>=1<<n)break;
for(int l=0; l<n; l++) {
if((s>>l)&1) {
sum+=mp[i][l];
}
}
tot[i+1][s]=sum;
// debug(sum);
}
}
int ans=0;
memset(dp,0,sizeof(dp));
for(int l=1; l<=n; l++) {
for(int i=0; v[0].size(); i++) {
int s=v[0][i];
if(s>=1<<n)break;
for(int j=0; j<v[s].size(); j++) {
int target=v[s][j];
if(target>=1<<n)break;
// cout<<s<<" "<<target<<endl;
// debug(tot[l][target]);
dp[l][target]=max(dp[l][target],dp[l-1][s]+tot[l][target]);
// if(target)debug(dp[l][target]);
ans=max(dp[l][target],ans);
}
}
}
cout<<ans<<endl;
}
return 0;
}
F - Working Time
不写下一个只贴个代码了。。。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<char, int> PCI;
const LL INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAX_N = (int)2e5+17;
const int MAX_M = (int)2e5+17;
int N, M, S, T, K, tp;
int a[MAX_N], b[MAX_N], lt[MAX_N];
int vis[MAX_N];
int main() {
// freopen("../data.in", "r", stdin);
//ios_base::sync_with_stdio(false);cin.tie(0);
scanf("%d", &T);
int kase = 1;
while (T --) {
scanf("%d %d", &N, &M);
int h = 0,m = 0;
for(int i = 0; i < N; i++) {
int q1,q2,w1,w2;
scanf("%d:%d %d:%d", &q1,&w1,&q2,&w2);
h += q2-q1-1;m += w2 + (60-w1);
}
h += m/60;
if(h >= M) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
} G - Hard Equation
扩展BSGS模板题
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=998244353;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
typedef long long LL;
inline LL gcd(LL a, LL b) {
return (!b) ? a : gcd(b, a % b);
}
inline void Exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) {
d = a, x = 1, y = 0;
} else {
Exgcd(b, a % b, d, y, x), y -= x * (a / b);
}
}
inline LL Solve(LL a, LL b, LL c) {// ax%c=b S.T. (a,c)=1
LL d, x, y;
Exgcd(a, c, d, x, y);
x = (x + c) % c;
return x * b % c;
}
inline LL Ksm(LL x, LL y, LL p) {
LL res = 1, t = x;
for(; y; y >>= 1) {
if (y & 1) res = res * t % p;
t = t * t % p;
}
return res;
}
#define mod 1313131
struct Hashset {
LL head[mod], next[maxn], f[maxn], v[maxn], ind;
void reset() {
ind = 0;
memset(head, -1, sizeof head);
}
void Insert(LL x, LL _v) {
LL ins = x % mod;
for(LL j = head[ins]; j != -1; j = next[j])
if (f[j] == x) {
v[j] = min(v[j], _v);
return;
}
f[ind] = x, v[ind] = _v;
next[ind] = head[ins], head[ins] = ind++;
}
LL operator [] (const LL &x) const {
LL ins = x % mod;
for(LL j = head[ins]; j != -1; j = next[j])
if (f[j] == x)
return v[j];
return -1;
}
} S;
LL BSGS(LL C, LL A, LL B, LL p) {// A^x%p=B S.T.(A,p)=1
if (p <= 100) {
LL d = 1;
for(int i = 0; i < p; ++i) {
if (d == B)
return i;
d = d * A % p;
}
return -1;
} else {
LL m = (int)sqrt(p);
S.reset();
LL d = 1, Search;
for(int i = 0; i < m; ++i) {
S.Insert(d, i);
d = d * A % p;
}
for(int i = 0; i * m < p; ++i) {
d = Ksm(A, i * m, p) * C % p;
Search = S[Solve(d, B, p)];
if (Search != -1)
return i * m + Search;
}
return -1;
}
}
int main() {
LL x, z, k;
register LL i, j;
int t;
scanf("%d",&t);
while(t--) {
scanf("%I64d%I64d%I64d", &x, &k, &z);
LL d = 1;
bool find = 0;
for(i = 0; i < 100; ++i) {
if (d == k) {
printf("%I64d\n", i);
find = 1;
break;
}
d = d * x % z;
}
if (find)
continue;
LL t, C = 1, num = 0;
bool failed = 0;
while((t = gcd(x, z)) != 1) {
z /= t;
k /= t;
C = C * x / t % z;
++num;
}
LL res = BSGS(C, x, k, z);
if (res == -1)
puts("No Solution");
else
printf("%I64d\n", res + num);
}
return 0;
}
| H | Gym 101853H |
| I | Gym 101853I |
答案。。。d*d/2
| J | Gym 101853J |
这3题就不贴代码了。水题（其实是懒得写。。。。。）
K - Citations
慢慢模拟
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<char, int> PCI;
const LL INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAX_N = (int)2e5+17;
const int MAX_M = (int)2e5+17;
int N, M, S, T, K, tp;
int a[MAX_N], b[MAX_N], lt[MAX_N];
int vis[MAX_N];
char s[21][322];
int main() {
scanf("%d", &T);
int kase = 1;
while (T--) {
scanf("%d", &N);getchar();
while(N--) {
for(int i = 0; i < 10; i++) {
fgets(s[i], sizeof(s[i]), stdin);
//printf("%s",s[i]);
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='a') {
vector<char> v;v.clear();
for(int j = 8; ; ) {
v.push_back(s[i][j]);
v.push_back(s[i][j+1]);
while(s[i][j] != ' ') j++;j++;
v.push_back(s[i][j]);
while(s[i][j] != ',' && s[i][j] != '}') j++;
if(s[i][j] == '}') break;
else j += 2;
}
for(int j = 0; j < v.size(); j+=3) {
printf("%c%c. %c%c ",v[j],v[j+1],v[j+2],(j+3<v.size())?',':'.');
}
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='t') {
for(int j = 7; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf(". ");
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='j') {
for(int j = 9; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf(". ");
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='y') {
for(int j = 6; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf(";");
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='v') {
for(int j = 8; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf("(");
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='n') {
for(int j = 8; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf("):");
break;
}
}
for(int i = 1; i <= 8; i++) {
if(s[i][0]=='p' && s[i][1]=='a') {
for(int j = 7; s[i][j] != '}'; j++) {
printf("%c",s[i][j]);
}
printf(".\n");
break;
}
}
}
}
return 0;
}
京公网安备 11010502036488号