1003 Ink on paper
Problem Description
Bob accidentally spilled some drops of ink on the paper. The initial
position of the i-th drop of ink is (xi,yi), which expands outward by
0.5 centimeter per second, showing a circle. The curious Bob wants to know how long it will take for all the inks to become connected. In
order to facilitate the output, please output the square of the time.
Input
The first line of input contains one integer T(1≤T≤5), indicating the
number of test cases. For each test case, the first line contains one
integer n(2≤n≤5000), indicating the number of ink on the paper. Each
of the next n lines contains 2 integers (xi,yi)(|xi|≤109,|yi|≤109),
indicating that x and y coordinates of the ink.
Output
For each test case, output one line containing one decimal, denoting the answer.
一道简单的最小生成树题,题面可以转化成在一个完全图上求最小生成树,直接使用Prim解决。
做的时候一直考虑的是二分法,误(
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll x,y;
}e[5010];
ll dis[5010];
int vis[5010];
int n;
ll prim()
{
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
ll ans = 0;
vis[1] = 1;
for(int i = 1; i <= n; i++)
if(!vis[i])
dis[i] = pow(abs(e[1].x-e[i].x),2)+pow(abs(e[1].y-e[i].y), 2);
for(int i = 1; i <= n; i++)
{
int flag = 0;
ll minn = 1e18+1;
for(int j = 1; j <= n; j++)
{
if(!vis[j] && dis[j] < minn)
{
flag = j,minn = dis[j];
}
}
ans = max(ans, dis[flag]);
vis[flag] = 1;
for(int j = 1; j <= n; j++)
{
if(!vis[j])
dis[j] = min(dis[j], (ll)pow(abs(e[flag].x-e[j].x),2) + (ll)pow(abs(e[flag].y-e[j].y),2));
}
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
ll op1,op2;
scanf("%lld%lld",&op1,&op2);
e[i].x = op1,e[i].y = op2;
}
printf("%lld\n",prim());
}
}
1006 GCD Game
Problem Description
Alice and Bob are playing a game.They take turns to operate. There are n numbers, a1 , a2 , … , an.
Every time, the player plays in 3 steps.
1.Arbitrarily chooses one number ai.
2.Arbitrarily chooses another number x(1≤x<ai).
3. Replace the number ai with gcd(ai,x). Here, gcd(u,v) refers to the Greatest Common Divisor of u and v.When a player can not make a single move he/she loses the game. Alice
moves the first and she asks you to tell her who will win the game if
both player play optimally.
Input
The first line contains a number T(1≤T≤100), the number of testcases.For each testcase, there are two lines. The first line contains one
number n(1≤n≤106). The second line contains n numbers a1 , a2 , … ,
an(1≤ai≤107).It is guaranteed that for all testcases, ∑n≤106.
Output
For each testcase, output the answer in one line. If Alice will win the game, print “Alice”, otherwise print “Bob”.
有关Nim博弈:https://blog.csdn/weixin_45113721/article/details/107018760
筛选质因子个数,然后Nim博弈。
先打个线性的表。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 1000;
bool is_prime[maxn];
ll prime[maxn], cnt = 0, fac[maxn];
void euler(int p)
{
is_prime[0] = is_prime[1] = 1;
for (ll i = 2; i <= p; ++i)
{
if (!is_prime[i])
prime[++cnt] = i, fac[i] = 1;
for (ll j = 1; j <= cnt && i * prime[j] <= p; ++j)
{
is_prime[i * prime[j]] = true;
fac[i * prime[j]] = 1 + fac[i];
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
euler(maxn - 100);
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
ll sg = 0;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d",&x);
sg ^= fac[x];
}
if (sg)
printf("Alice\n");
else
printf("Bob\n");
}
}
1009 Singing Superstar
Problem Description
Ke Ke is a cheerful, enthusiastic girl. She dreams of singing happily
every day. One day, while practicing singing, Ke Ke accidentally
discovered that there are some words that can make the song better.
She called these words “SuperstarWords”.After a lot of attempts, she found that in each song, there are a
total of n “SuperstarWords”. She wants to know the maximum number of
disjoint occurrences of each “SuperstarWords” in her song.Note : one occurrence means that the SuperstarWord is a continuous
substring of the song at a certain position.For example: The maximum number of disjoint occurrences of “aba” in
“abababa” is 2
Input
The first line contains an integer T(T≤5), denoting the number of test
cases.The first line of each test case contains one string s(1≤|s|≤105),
denoting a song.The second line of each test case contains one integer n(1≤n≤105),
denoting the number of SuperstarWordsThe next n lines contains contains one string ai(1≤ |ai| ≤30),
denoting one SuperstarWordsIt is guaranteed that for all test cases, ∑|s|≤4∗105, ∑|ai|≤4∗105
Note:All input string character sets are lowercase English letters
Output
For each test case, output n lines, each line has one integer, indicating the answer.
大意:
问在串T中出现了几次不相交的串S?
每次有n个串S询问
一道简单的字符串题,对母串中所有长度小于等于30的串做字符串哈希,对相同哈希值的串暴力统计答
案,每个询问直接查询对应哈希值的答案。
也可以使用Trie/AC自动机来通过本题,数据范围放的很松,理论复杂度稍劣也能通过。
更多推荐
杭电多校总结2021-08-12
发布评论