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
using namespace std;
typedef long long ll;
const long long mod = 1e9 + ;
const int N = 2e5 + ;
int main()
{
ll n;
cin >> n;
if (n == )
{
cout << << endl;
return ;
}
n++;
if (n % == )
{
cout << n / << endl;
}
else
{
cout << n << endl;
}
}
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
using namespace std;
typedef long long ll;
const long long mod = 1e9 + ;
const int N = 2e5 + ;
string a, b, c;
string str[];
int num[][];
int ansermaxn[];
int main()
{
ll n;
cin >> n;
for (int i = ; i <= ; i++)
{
cin >> str[i];
}
int aim = ;
int ansermax = -;
int ansnow;
for (int i = ; i <= ; i++)
{
for (int j = ; j < str[i].size(); j++)
{
num[i][str[i][j]]++;
}
}
for (int i = ; i <= ; i++)
{
for (int j = ; j <= ; j++)
{
if (num[i][j] + n <= str[i].size())
{
ansnow = num[i][j] + n; if (ansnow > ansermax)
{
aim = i;
ansermax = ansnow;
}
}
else
{
if (num[i][j] == str[i].size())
{
if (n == )
{
ansnow = str[i].size() - ;
}
else
{
ansnow = str[i].size();
}
}
else
{
ansnow = str[i].size();
}
if (ansnow > ansermax)
{
aim = i;
ansermax = ansnow;
}
}
ansermaxn[i] = max(ansermaxn[i], ansnow);
}
}
int cnt = ;
for (int i = ; i <= ; i++)
{
//cout << ansermaxn[i] << endl;
if (ansermaxn[i] == ansermax)
{
cnt++;
}
}
if (cnt > )
{
cout << "Draw" << endl;
return ;
}
if (aim == )
{
cout << "Kuro" << endl;
}
else if (aim == )
{
cout << "Shiro" << endl;
}
else
{
cout << "Katie" << endl;
}
}
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
using namespace std;
typedef long long ll;
const long long mod = 1e9 + ;
const int N = 3e5 + ;
vector<int> gra[N];
ll anser = ;
ll reduce = ;
ll number1 = ;
ll number2 = ;
ll number = ;
int flag = ;
void dfs(int x, int pre, int aim, int flag)
{
if (flag)
{
number++;
}
int len = gra[x].size();
for (int i = ; i < len; i++)
{
int to = gra[x][i];
if (to == pre)
{
continue;
}
if (to == aim)
{
dfs(to, x, aim, );
}
else
{
dfs(to, x, aim, flag);
}
}
}
int main()
{
int n;
cin >> n;
int x, y;
int u, v;
cin >> x >> y;
for (int i = ; i <= n - ; i++)
{
scanf("%d %d", &u, &v);
gra[u].pb(v);
gra[v].pb(u);
}
anser = 1LL * (n - ) * n;
dfs(x, -, y, );
number1 = number;
number = ;
dfs(y, -, x, );
number2 = number;
anser -= 1LL * number2 * number1;
cout << anser << endl;
}
D
一开始给你一个空的集合
有两种操作:
①集合中加入一个数字X
②询问给你三个数字Xi Ki Si 查找集合中是否存在数字V满足 ① Ki是Xi和V的因子 ② V<=Si-Ki 当如果有多个满足条件的数输出Xi Xor V最大的那个V
解:
01字典树暴力操作
直接每次insert一个未出现过的数的时候 暴力Insert到每个它的因子里面去
复杂度为:1e5*ln(1e5)*位数(最多为18)=1e7
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
vector<int>G[maxn];
int vis[maxn];
void read(int &x)
{
x = ;
char c = getchar();
while (c > '' || c < '')
{
c = getchar();
}
while (c >= '' && c <= '')
{
x = (x << ) + (x << ) + c - '', c = getchar();
}
}
struct Trie //01字典树指针版
{
struct node
{
int Min, val;
node *ch[];
node()
{
Min = maxn; //维护一个最小值
ch[] = ch[] = NULL;
}
}*rt[maxn];
void init()
{
for (int i = ; i < maxn; i++)
for (int j = i; j < maxn; j += i) //复杂度1e5*ln1e5=1e6
{
G[j].push_back(i); //把一个数的因子全部push进去
}
for (int i = ; i < maxn; i++)
{
rt[i] = new node; //每个数赋予一个新指针
}
}
void insert(int x)
{
int Len = G[x].size(); //插入一个数
for (int i = ; i < Len; i++)
{
node *cur = rt[G[x][i]]; //暴力枚举insert到这个数的每个因子里面取
cur->Min = min(cur->Min, x); //维护最小值
for (int j = ; j >= ; j--) //争取取每位^1的使之异或值最大
{
if (cur->ch[x >> j & ] == NULL) //如果没有的话创造一个新节点
{
cur->ch[x >> j & ] = new node;
}
cur = cur->ch[x >> j & ];
cur->Min = min(cur->Min, x); //每个节点维护最小值
}
cur->val = x; //最后一个节点的值为x 最后取答案用
}
}
int query(int x, int k, int s)
{
if (x % k != ) //如果k是x和v的gcd的因子的话 x和v都是k的倍数
{
return -;
}
node *cur = rt[k]; //
if (cur->Min > s - x) //如果最小的都不能满足的话 不存在
{
return -;
}
for (int i = ; i >= ; i--)
{
int tb = x >> i & ;
if (cur->ch[tb ^ ] != NULL && cur->ch[tb ^ ]->Min <= s - x) //如果^1的值满足条件
{
cur = cur->ch[tb ^ ];
}
else
{
cur = cur->ch[tb];
}
}
return cur->val; //返回使之异或值最大的数列值
}
} T;
int main()
{
int N, i, j, opt, x, k, s;
T.init();
read(N);
while (N--)
{
read(opt);
if (opt == )
{
read(x);
if (!vis[x])
{
vis[x] = , T.insert(x);
}
}
else
{
read(x);
read(k);
read(s);
printf("%d\n", T.query(x, k, s));
}
}
return ;
}
