zj集训 8.5
程序员文章站
2022-06-03 13:18:03
...
Day 5
300.5
忘记上闹钟起晚了…
T1 输油管道
Solution
bfs搜索断点，对于断点枚举可以填的颜色，用bfs判断能不能联通。
#include <cstdio>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int N = 30;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
char a[N][N];
int n,m,sx,sy,ex,ey;
int ansx,ansy;
char anst;
struct sta{
int x,y;
int lx,ly;
};
char read(){
char ch=getchar();
while(ch!='.' && ch!='M' && ch!='Z' && ch!='|' && ch!='-' && ch!='+' && (ch<'1' || ch>'4')){
ch=getchar();
}
return ch;
}
queue<sta> q;
sta cal(sta u){
int x=u.x;
int y=u.y;
int lx=u.lx;
int ly=u.ly;
char typ=a[x][y];
if(typ=='|'){
if(abs(x-lx)!=1 || y!=ly){
return (sta){-1, -1, -1, -1};
}
return (sta){(x<<1)-lx, y, x, y};
}
else if(typ=='-'){
if(abs(y-ly)!=1 || x!=lx){
return (sta){-1, -1, -1, -1};
}
return (sta){x, (y<<1)-ly, x, y};
}
else if(typ=='+'){
if((abs(lx-x)==1 && ly==y) || (abs(ly-y)==1 && lx==x)){
if(lx==x){
return (sta){x, (y<<1)-ly, x, y};
}
else if(ly==y){
return (sta){(x<<1)-lx, y, x, y};
}
}
else{
return (sta){-1, -1, -1, -1};
}
}
else if(typ=='1'){
if((lx-x==1 && ly==y) || (ly-y==1 && lx==x)){
if(lx==x){
return (sta){x+1, y, x, y};
}
else if(ly==y){
return (sta){x, y+1, x, y};
}
}
else{
return (sta){-1, -1, -1, -1};
}
}
else if(typ=='2'){
if((x-lx==1 && ly==y) || (ly-y==1 && lx==x)){
if(lx==x){
return (sta){x-1, y, x, y};
}
else if(ly==y){
return (sta){x, y+1, x, y};
}
}
else{
return (sta){-1, -1, -1, -1};
}
}
else if(typ=='3'){
if((x-lx==1 && ly==y) || (y-ly==1 && lx==x)){
if(lx==x){
return (sta){x-1, y, x, y};
}
else if(ly==y){
return (sta){x, y-1, x, y};
}
}
else{
return (sta){-1, -1, -1, -1};
}
}
else if(typ=='4'){
if((lx-x==1 && ly==y) || (y-ly==1 && lx==x)){
if(lx==x){
return (sta){x+1, y, x, y};
}
else if(ly==y){
return (sta){x, y-1, x, y};
}
}
else{
return (sta){-1, -1, -1, -1};
}
}
}
bool check(){
int firx=0,firy=0;
for(int i=0; i<4; i++){
int nx=sx+dx[i];
int ny=sy+dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]!='.'){
firx=nx;
firy=ny;
break;
}
}
q.push((sta){firx, firy, sx, sy});
while(!q.empty()){
sta u=q.front();
q.pop();
if(u.x==ex && u.y==ey){
return 1;
}
sta v=cal(u);
if(v.x<1 || v.x>n || v.y<1 || v.y>m){
return 0;
}
if(a[v.x][v.y]!='.'){
q.push(v);
}
else{
return 0;
}
}
}
void work(){
a[ansx][ansy]='|';
if(check()){
anst='|';
return;
}
a[ansx][ansy]='-';
if(check()){
anst='-';
return;
}
a[ansx][ansy]='+';
if(check()){
anst='+';
return;
}
a[ansx][ansy]='1';
if(check()){
anst='1';
return;
}
a[ansx][ansy]='2';
if(check()){
anst='2';
return;
}
a[ansx][ansy]='3';
if(check()){
anst='3';
return;
}
a[ansx][ansy]='4';
if(check()){
anst='4';
return;
}
}
void bfs(){
int firx=0,firy=0;
for(int i=0; i<4; i++){
int nx=sx+dx[i];
int ny=sy+dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]!='.'){
firx=nx;
firy=ny;
break;
}
}
if(firx==0 && firy==0){
ansx=sx;
ansy=sy;
work();
return;
}
q.push((sta){firx, firy, sx, sy});
while(!q.empty()){
sta u=q.front();
q.pop();
sta v=cal(u);
if(a[v.x][v.y]!='.'){
q.push(v);
}
else{
ansx=v.x;
ansy=v.y;
break;
}
}
work();
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
a[i][j]=read();
if(a[i][j]=='M'){
sx=i;
sy=j;
}
else if(a[i][j]=='Z'){
ex=i;
ey=j;
}
}
}
bfs();
printf("%d %d %c\n",ansx,ansy,anst);
return 0;
}
T2 数码问题
Solution
我们发现n大k小。我们不需要知道每个点的位置，只需要知道k个的位置。
对于一个数的移动，修改移动影响的数的坐标。
#include <cstdio>
#include <iostream>
#define int long long
using namespace std;
const int N = 10010;
const int K = 1010;
int n,k,ans;
struct node{
int num,x,y,ex,ey;
}a[K];
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1; i<=k; i++){
scanf("%lld%lld%lld",&a[i].num,&a[i].ex,&a[i].ey);
a[i].x=(a[i].num-1)/n+1;
a[i].y=(a[i].num-1)%n+1;
}
for(int i=1; i<=k; i++){
int dy=(a[i].ey-a[i].y+n)%n;
a[i].y=(a[i].y+dy-1)%n+1;
ans+=dy;
for(int j=1; j<=k; j++){
if(i==j){
continue;
}
if(a[j].x==a[i].x){
a[j].y=(a[j].y+dy-1)%n+1;
}
}
int dx=(a[i].ex-a[i].x+n)%n;
a[i].x=(a[i].x+dx-1)%n+1;
ans+=dx;
for(int j=1; j<=k; j++){
if(i==j){
continue;
}
if(a[j].y==a[i].y){
a[j].x=(a[j].x+dx-1)%n+1;
}
}
printf("%lld\n",ans);
ans=0;
}
return 0;
}
T3 灌水
Description
学生都很喜欢灌水，第一天只有Alice给她的每个朋友灌了一次水，从第二天开始，所有学生（包括Alice）将会有规律地去灌水：
•如果前一天被灌了奇数次的水，他们将会给每个朋友灌一次水；
•如果前一天被灌了偶数次的水，他们将会给每个朋友灌两次水。
学生编号为1到N，Alice为1号，学生之间的朋友关系会给出。
计算H天后一共灌了几次水。
Input
输入一行包含两个整数N和H(1<=N<=20,1<=H<=10^9)，表示学生数和天数。
接下来N行，每行包含N个‘0’或‘1’，（A,B）处的字符表示A和B的关系，‘1’表示是朋友关系，‘0’表示不是。注意自己和自己不是朋友关系，输入保证该矩阵是对称的。
Output
输出H天后一共灌水的数量。
Sample Input
输入1：
4 1
0110
1001
1001
0110
输入2：
4 2
0110
1001
1001
0110
输入3：
5 3
01000
10110
01000
01001
00010
Sample Output
输出1：
2
输出2：
14
输出3：
26
Data Constraint
Hint
【样例解释】
样例2中，第一天Alice灌了2次水，第二天学生1和学生4给学生2和学生3都灌了2次水，而学生2和学生3给学生1和学生4各灌水1次，2天一共灌了12次水。
【数据范围】
50%的数据 H<=1000。
Solution
对每个人对他的朋友+1还是+2装压，一定会有循环节。
#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 25;
const int M = 1000001;
int n,h,ans;
int l,r;
int a[N][N];
int s[M];
int ansp[M];
int last[N],tmp[N];
int read(){
char ch=getchar();
if(ch!='0' && ch!='1'){
ch=getchar();
}
return ch-'0';
}
signed main(){
freopen("data10.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%lld%lld",&n,&h);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
a[i][j]=read();
}
}
for(int i=1; i<=n; i++){
if(a[1][i]){
ans++;
tmp[i]++;
}
}
for(int t=2; t<=h; t++){
memcpy(last, tmp, sizeof last);
memset(tmp, 0, sizeof tmp);
for(int i=1; i<=n; i++){
int add=0;
if(last[i] & 1){
add=1;
s[t] |= 1<<i;
}
else{
add=2;
}
for(int j=1; j<=n; j++){
if(a[i][j]){
tmp[j]+=add;
ans+=add;
ansp[t]+=add;
}
}
}
bool flag=0;
for(int i=2; i<=t-1; i++){
if(s[i]==s[t]){
flag=1;
l=i;
r=t-1;
break;
}
}
printf("Day %d: %d\n",t,s[t]);
if(flag){
ans-=ansp[t];
break;
}
}
if(l && r){
int sum=0;
for(int i=l; i<=r; i++){
sum+=ansp[i];
}
ans+=sum*((h-r)/(r-l+1));
int left=(h-r)%(r-l+1);
for(int i=l; i<=l+left-1; i++){
ans+=ansp[i];
}
}
printf("%lld\n",ans);
return 0;
}
T4 开花
Solution
线段树模板
#include <cstdio>
#include <iostream>
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
const int N = 100010;
typedef pair<int,int> p;
int n,m;
int tr[N<<2],lz[N<<2];
p q[N];
void push_up(int k){
tr[k]=tr[ls(k)]+tr[rs(k)];
}
void push_down(int k,int l,int r){
int mid=(l+r)>>1;
tr[ls(k)]+=(mid-l+1)*lz[k];
tr[rs(k)]+=(r-mid)*lz[k];
lz[ls(k)]+=lz[k];
lz[rs(k)]+=lz[k];
lz[k]=0;
}
void update(int k,int l,int r,int L,int R,int x){
if(L<=l && r<=R){
tr[k]+=(r-l+1)*x;
lz[k]+=x;
return;
}
int mid=(l+r)>>1;
if(L<=mid){
update(ls(k), l, mid, L, R, x);
}
if(R>mid){
update(rs(k), mid+1, r, L, R, x);
}
push_up(k);
}
int query(int k,int l,int r,int P){
if(l==r){
return tr[k];
}
if(lz[k]){
push_down(k, l, r);
}
int mid=(l+r)>>1;
if(P<=mid){
return query(ls(k), l, mid, P);
}
else{
return query(rs(k), mid+1, r, P);
}
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d%d",&q[i].first,&q[i].second);
m=max(m, q[i].second);
}
for(int i=1; i<=n; i++){
int l=q[i].first;
int r=q[i].second;
int x=query(1, 1, m, l);
int y=query(1, 1, m, r);
update(1, 1, m, l, l, -x);
update(1, 1, m, r, r, -y);
update(1, 1, m, l+1, r-1, 1);
printf("%d\n",x+y);
}
return 0;
}