题目链接：http://codeforces.com/contest/761
A. Dasha and Stairs
题意：给定奇数偶数个数寻找一个满足条件的队列，很显然，奇偶数相差必须为不超过1才行。
解法：
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
scanf("%d%d",&a,&b);
if(a==0&&b==0) puts("NO");
else if(abs(a-b)<=1) puts("YES");
else puts("NO");
return 0;
}B. Dasha and friends
题意：有两个人在任意一个起点逆时针奔跑，这个圈长度为L，其中有N个障碍点，给出每个人逆时针奔跑的时候跑多长距离会遇到一个障碍物，问两人跑的是否是一个地图。
解法：自己O(n^2)枚举出发的位置暴力即可，数据范围大也是可以做，可以用最小表示法。
#include <bits/stdc++.h>
using namespace std;
int n,L;
bool vis[110];
int b[110];
int main(){
scanf("%d%d",&n,&L);
for(int i=1; i<=n; i++){
int x;
scanf("%d", &x);
vis[x]=1;
}
for(int i=1; i<=n; i++) scanf("%d", &b[i]);
for(int i=1; i<=L; i++){
bool ok = 1;
for(int j=1; j<=n; j++){
int tmp=i+b[j];
tmp=(tmp+L)%L;
if(!vis[tmp]){
ok=0;break;
}
}
if(ok==1){
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}C. Dasha and Password
题意：有n个串，每个串有m个字符，可以由数字，小写字母，和三个符号组成，现在要在这n个串中每个串找出一个字符组成一个密码，这密码要求至少要有一个数字，一个字母和一个特殊字符，一开始每个字符串都指在第一个字符，每次移动可以往两边移动，也就是说可以往左右两边移动，要求所得到的密码移动的次数最少。
解法：要求最少的次数，所以移动最少的串，每个串移动最少的次数就行了，所以要求三个至少，所以我们可以找出三个串，每个串移动来找到一个条件，最后枚举最多50*49*48种情况，三个for循环就行。
#include <bits/stdc++.h>
using namespace std;
string s[55];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
}
int ans=1e9;
for(int i=0; i<n; i++){//digit
for(int j=0; j<n; j++){//lowercase
for(int k=0; k<n; k++){//'#','*','&'
if(i==j||i==k||j==k) continue;
int sz = s[i].size();
int d1 = 1e9;
for(int l=0; l<sz; l++){
if(isdigit(s[i][l])){
d1 = min(d1, min(l, sz-l));
}
}
sz = s[j].size();
int d2 = 1e9;
for(int l=0; l<sz; l++){
if(islower(s[j][l])){
d2 = min(d2, min(l, sz-l));
}
}
sz = s[k].size();
int d3 = 1e9;
for(int l=0; l<sz; l++){
if(s[k][l]=='#'||s[k][l]=='*'||s[k][l]=='&'){
d3 = min(d3, min(l, sz-l));
}
}
if(d1==1e9||d2==1e9||d3==1e9) continue;
ans = min(ans, d1+d2+d3);
}
}
}
printf("%d\n", ans);
return 0;
}D. Dasha and Very Difficult Problem
题意：：序列bi=ci+ai,给出ai和将ci离散化后的pi，问在l，r中能否找出这样一个任意解。
解法：通过ci和pi，我们可以得到bi的最小情况，通过平移区间，将bi平移到l，r内即可。
#include<iostream>
#include<iostream>
using namespace std;
int n, l, r;
int a[100005];
int b[100005];
int p[100005];
int main()
{
cin >> n >> l >> r;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> p[i];
int ma = - 1e9 + 5, mi = 1e9 + 5;
for (int i = 0; i < n; ++i)
{
b[i] = a[i] + p[i];
ma = max(ma, b[i]);
mi = min(mi, b[i]);
}
if (ma - mi > r - l)
cout << "-1";
else
{
int temp;
if (mi < l)
temp = l - mi;
else temp = r - ma;
for (int i = 0; i < n; ++i)
cout << b[i] + temp << " ";
}
}E. Dasha and Puzzle
题意：给你一棵树，让你在二维平面上摆出来，边必须平行坐标轴，且边没有交集
解法：
如果存在某点度数大于4肯定不行。
然后，第一层让边长为len，第二层边长为len/2，第三层边长为len/4……
这样弄下去就好了，这样就保证每一层都不会碰到上一层了。即缩小距离的方法。#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 40;
const int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
struct edge{
int to,next;
edge(){}
}E[maxn*2];
int n, head[maxn],du[maxn], edgecnt;
void init(){
memset(head,-1,sizeof(head));
edgecnt=0;
}
void add(int u, int v){
E[edgecnt].to = v, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
pair <LL,LL> ans[maxn];
void dfs(int u, int fa, LL x, LL y, LL dis, int dir){
int j=0;
ans[u] = {x, y};
for(int i=head[u];~i;i=E[i].next){
int v = E[i].to;
if(v == fa) continue;
if(j+dir==3) j++;
dfs(v, u, x+d[j][0]*dis, y+d[j][1]*dis, dis/2, j);
j++;
}
}
int main(){
init();
scanf("%d", &n);
for(int i=1; i<n; i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
du[x]++;
du[y]++;
}
for(int i=1; i<=n; i++){
if(du[i]>4){
return 0*printf("NO\n");
}
}
printf("YES\n");
dfs(1, 0, 0, 0, 1<<30, -1);
for(int i=1; i<=n; i++){
printf("%lld %lld\n", ans[i].first, ans[i].second);
}
return 0;
}F. Dasha and Photos
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1002;
const int maxq = 3e5+10;
struct node{
int u1,v1,u2,v2,c;
}q[maxq];
int a[maxn][maxn], cnt[26][maxn][maxn];//cnt(c,i,j)为(i,j)在给定的子矩阵中且变成的字符是c的图的个数
//f[i][j]为所有图(i,j)位置与原图(i,j)位置距离之和:sum1(i,j)=sigma(c='a' to 'z')cnt1(c,i,j)*abs(c-a[i][j])
//sum1[i][j]为f从(1,1)到(i,j)的前缀和
//cnt2[c][i][j]为(i,j)是c的图的个数(不要求(i,j)在给定的子矩阵中)
//sum2[c][i][j]为cnt2的二维前缀和
LL sum1[maxn][maxn], sum2[26][maxn][maxn];
int n,m,K;
int main(){
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=n;i++){
char str[maxn];
scanf("%s", str+1);
for(int j=1;j<=m;j++){
a[i][j]=str[j]-'a';
}
}
for(int i=1;i<=K;i++){
char typ[3];
scanf("%d %d %d %d", &q[i].u1,&q[i].v1,&q[i].u2,&q[i].v2);
scanf("%s", typ);
q[i].c = typ[0]-'a';
++cnt[q[i].c][q[i].u1][q[i].v1];
--cnt[q[i].c][q[i].u1][q[i].v2+1];
--cnt[q[i].c][q[i].u2+1][q[i].v1];
++cnt[q[i].c][q[i].u2+1][q[i].v2+1];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
LL fij, tot;
fij = 0;
tot = K;
for(int c=0; c<26; c++){
cnt[c][i][j] += cnt[c][i-1][j];
cnt[c][i][j] += cnt[c][i][j-1];
cnt[c][i][j] -= cnt[c][i-1][j-1];
fij += cnt[c][i][j]*abs(a[i][j]-c);
tot -= cnt[c][i][j];
}
sum1[i][j]=fij+sum1[i-1][j]+sum1[i][j-1]-sum1[i-1][j-1];
for(int c=0; c<26; c++){
sum2[c][i][j]=cnt[c][i][j]+sum2[c][i-1][j]+sum2[c][i][j-1]-sum2[c][i-1][j-1];
if(a[i][j]==c){
sum2[c][i][j] += tot;
}
}
}
}
LL sum, ans = 1e18;
for(int i=1; i<=K; i++){
int u1 = q[i].u1, v1 = q[i].v1, u2 = q[i].u2, v2 = q[i].v2, c0 = q[i].c;
sum = sum1[n][m]-(sum1[u2][v2]-sum1[u1-1][v2]-sum1[u2][v1-1]+sum1[u1-1][v1-1]);
for(int c=0; c<26; c++){
sum += (sum2[c][u2][v2]-sum2[c][u1-1][v2]-sum2[c][u2][v1-1]+sum2[c][u1-1][v1-1])*abs(c-c0);
}
ans = min(ans, sum);
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号