11.7日志
很简单的一道构造题,容易发现吃r最多的和吃r最少的差值不会超过1,因为每只鸡肯定能吃sum / k,剩下的sum % k一定是少于k的那么我们就分给1 ~ sum % k一只一颗即可,这样一来最少的吃了sum / k,最多的吃了sum / k + 1,接下来就是进行分配,我们将每只鸡吃的米的数量装进一个桶中,遇到一个R就-1一直到桶空并且遇到新的R的时候换成下一个桶,难点在于如何使得每只鸡吃的范围都是一个连通块呢,也很简单我们只需要在i % 2的时候从左往右遍历i % 2 == 0的时候从右往左遍历这样就不会出现首位断开的情况了
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<string , string> pss;
const int N = 5e3 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
string s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int r,c,k;
int mp[100];
char a[200][200],ans[200][200];
void work()
{
cin>>r>>c>>k;
memset(mp , 0 , sizeof mp);
int sum = 0;
for(int i = 1 ; i <= r ; i++)
{
for(int j = 1 ; j <= c ; j++)
{
cin>>a[i][j];
if(a[i][j] == 'R')
{
sum++;
}
}
}
for(int i = 0 ; i < k ; i++)
{
mp[i] += sum / k;
if(i < sum % k)
{
mp[i]++;
}
}
int cnt = 0;
for(int i = 1 ; i <= r ; i++)
{
if(i % 2)
{
for(int j = 1 ; j <= c ; j++)
{
if(a[i][j] == 'R')
{
if(!mp[cnt])
{
cnt++;
}
mp[cnt]--;
}
ans[i][j] = s[cnt];
}
}else
{
for(int j = c ; j >= 1 ; j--)
{
if(a[i][j] == 'R')
{
if(!mp[cnt])
{
cnt++;
}
mp[cnt]--;
}
ans[i][j] = s[cnt];
}
}
}
for(int i = 1 ; i <= r ; i++)
{
for(int j = 1 ; j <= c ; j++)
{
cout<<ans[i][j];
}
cout<<"\n";
}
}
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t ;
while(t--)
{
work();
}
}
感觉就是一道思维题,比起考虑每个圆对答案的贡献我们可以先考虑每一个单位面积对答案的贡献,我们可以发现每一个单位面积只要被圆覆盖那么要么会被计算1次要么会被计算2次,什么时候被计算1次什么时候被计算2次呢,我们可以发现若这个单位面积被偶数个圆覆盖了那么我们一定可以拆分成1 + 奇数两个图,也就是说可以被计算两次,若是被覆盖奇数次那么我们只能拆分成奇数 + 偶数个圆覆盖次数,那么就最多只能被计算1次了,但我们不可能遍历整张图所以我们还是要从圆入手,我们先对圆按照r进行升序排列然后双重循环对于i遍历1 ~ i - 1看有多少圆j是被i覆盖的,若被覆盖那么就对j进行一次计数并且从i的面积中减去j的面积因为j的这块面积之后会在算j的时候被计算,之后只需要对每个被处理后的圆看它被覆盖次数的奇偶性来进行分类讨论即可,注意每个圆一开始覆盖次数都是一次(被自己覆盖),还有就是开ll
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<string , string> pss;
const int N = 5e3 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;
struct node
{
ll x,y,r;
double s;
}a[N];
double f(ll x,ll y,ll xx,ll yy)
{
return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
bool cmp(node a,node b)
{
return a.r < b.r;
}
int n;
double ans;
int st[N];
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i = 1 ; i <= n ; i++)
{
cin>>a[i].x>>a[i].y>>a[i].r;
st[i] = 1;
a[i].s = a[i].r * 1.0 * a[i].r * pi;
}
sort(a + 1 , a + n + 1 , cmp);
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j < i ; j++)
{
if(i == j)
{
continue;
}else
{
ll x1 = a[i].x,y1 = a[i].y,r1 = a[i].r,x2 = a[j].x,y2 = a[j].y,r2 = a[j].r;
double dist = f(x1 , y1 , x2 , y2);
if(dist < r1 + r2)
{
if(r1 > r2)
{
st[j]++;
a[i].s -= a[j].s;
}else
{
st[i]++;
a[j].s -= a[i].s;
}
}
}
}
}
for(int i = 1 ; i <= n ; i++)
{
if(st[i] % 2 == 0)
{
ans += 2 * a[i].s;
}else
{
ans += a[i].s;
}
}
printf("%.8lf",ans);
}
首先需要考虑双重异或如何化简,若要死算这是一个n^2复杂度的算法,并且我们需要知道所有i -> j的异或信息这也是一个需要n^2复杂度才能解决的问题,但是我们发现从i -> j的异或信息其实就等于1 -> i 异或上 1 -> j因为a 异或 a = 0所以当i和j在同一个子树中的时候dist[i]^dist[j]会消去1到lca(i , j)之间的异或信息只保留我们需要的i到j的异或信息,那么我们只需要从1做一次dfs得到1到任何一个节点的异或信息就可以通过一次运算得到i到j的异或信息,接下来我们只需要看我们数组中每个位置出现的次数,若是奇数则需要抑或上dist[i]否则可以直接跳过
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;
int n,m,l;
string dist[N];
vector <pis> g[N];
int b[N],cnt[N];
string f(string a,string b)
{
string res;
for(int i = 0 ; i < a.size() ; i++)
{
if(a[i] == b[i])
{
res += '0';
}else
{
res += '1';
}
}
return res;
}
void dfs(int u,int fa,string s)
{
dist[u] = s;
for(int i = 0 ; i < g[u].size() ; i++)
{
int j = g[u][i].x;
string ss = g[u][i].y;
if(j == fa)
{
continue;
}
dfs(j , u , f(s , ss));
}
}
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>l;
for(int i = 1 ; i < n ; i++)
{
int u,v;
string a;
cin>>u>>v>>a;
g[u].push_back({v , a});
g[v].push_back({u , a});
}
string st,ans;
for(int i = 0 ; i < l ; i++)
{
st += '0';
ans += '0';
}
dfs(1 , -1 , st);
for(int i = 1 ; i <= m ; i++)
{
cin>>b[i];
}
for(int i = 1 ; i <= m ; i++)
{
cnt[i] += max(0 , m - i - 1) + max(0 , i - 2);
if(cnt[i] % 2)
{
ans = f(ans , dist[b[i]]);
}
}
cout<<ans;
}
原文地址：https://blog.csdn.net/2302_79370417/article/details/143453391
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！