T1
思路
考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) - 1的所有数就行了。
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n,m,K,a[N],b[N],k[N];
int gcd(int x,int y) {
return !y ? x : gcd(y,x % y);
}
namespace BF1 {
void Main() {
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int aa = read();
for(int i = 1;i <= aa;++i) a[read()] = 1;
int bb = read();
for(int i = 1;i <= bb;++i) b[read()] = 1;
read();
for(int i = 0;i <= 100000;++i) {
int x1 = i % n, x2 = i % m;
a[x1] = b[x2] = a[x1] | b[x2];
}
for(int i = 0;i < n;++i) {
if(a[i] != 1) {
puts("No");
return;
}
}
for(int i = 0;i < m;++i) {
if(b[i] != 1) {
puts("No");
return;
}
}
puts("Yes");
}
}
namespace BF2 {
int tmp[N * 5],js = 0;
void Main() {
js = 0;
int mod = gcd(gcd(n,m),K);
int aa = read();
for(int i = 1;i <= aa;++i) tmp[++js] = read() % mod;
int bb = read();
for(int i = 1;i <= bb;++i) tmp[++js] = read() % mod;
int kk = read();
for(int i = 1;i <= kk;++i) tmp[++js] = read() % mod;
int now = 0;
sort(tmp + 1,tmp + js + 1);
tmp[0] = -1;
int ans = 0;
for(int i = 1;i <= js;++i) {
if(tmp[i] == tmp[i-1]) continue;
if(tmp[i] == tmp[i-1]+1) now++;
else {
ans = max(ans,now);
now = 1;
}
}
ans = max(ans,now);
if(ans >= mod) puts("Yes");
else puts("No");
return;
}
}
int main() {
freopen("happy2.in","r",stdin);
freopen("happy2.out","w",stdout);
int T = read();
while(T--) {
n = read(),m = read(),K = read();
if(n <= 100 && m <= 100 && K == 0) {
BF1::Main();
continue;
}
BF2::Main();
}
return 0;
}
T2
想了一会感觉不可做,直接55分暴力。
55分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 300000 + 100;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n,p;
namespace BF1 {
int du[N];
void Main() {
for(int i = 1;i <= n;++i) {
int x = read(), y = read();
du[x]++;
du[y]++;
}
ll ans1 = 0;
for(int i = 1;i <= n;++i)
if(du[i] == 0) ans1++;
cout<<(ll)n * (ll)(n - 1)/2 - (ans1 * (ans1 - 1) / 2);
return;
}
}
namespace BF2 {
const int NN = 110;
bitset <NN> tmp[NN];
int ans = 0;
inline int check(int x,int y) {
bitset <NN> ls;
ls = tmp[x] | tmp[y];
return ls.count() >= p;
}
void Main() {
for(int i = 1;i <= n;++i) {
int x = read(),y = read();
tmp[x][i] = 1;
tmp[y][i] = 1;
}
for(int i = 1;i <= n;++i) {
for(int j = i + 1;j <= n;++j) {
ans += check(i,j);
}
}
cout<<ans<<endl;
}
}
int main() {
freopen("suspect.in","r",stdin);
freopen("suspect.out","w",stdout);
n = read(),p = read();
if(p == 0) {
cout<<((ll)n*(n-