具体模型

ACM
, ,

偶尔碰到很难写的题目,把代码贴在下面备用.

光线折射

abc431e:代码实现了从00的左侧入射,经过ABC三种不同的棱镜反射,代价是1个金币能够改变一个格子的棱镜类型,最后到达nm右侧求最小代价.

1
A:无      B:\       C:/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int x,y,dir,d;};
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};//方向
int f(int dir,char c){if(c=='A') return dir;if(c=='B') return dir^1;return dir^3;}//转向
void solve(){
	int n,m,ndir,nx,ny,nd;
	cin>>n>>m;
	vector<string>v(n+3);
	vector<vector<vector<int>>>dis(n+3,vector<vector<int>>(m+3,vector<int>(4,1e18)));
	for(int i=1;i<=n;i++) cin>>v[i],v[i]=" "+v[i];
	if(n==1&&m==1){//细节 1
		if(v[1][1]=='A') cout<<"0\n";
		else cout<<"1\n";
		return;
	}
	deque<node>q;
	q.push_front({1,2,0,(v[1][1]!='A')});
	q.push_front({2,1,1,(v[1][1]!='B')});
	dis[1][2][0]=(v[1][1]!='A');
	dis[2][1][1]=(v[1][1]!='B');
	int ans=1e18;
	while(!q.empty()){
		auto [x,y,dir,d]=q.front();q.pop_front();
		if(x>n||y>m||x<1||y<1) continue;//细节 4
		if(ans+1<d) break;
		if(x==n&&y==m) ans=min(ans,d+(f(dir,v[n][m])!=0));//细节 2
		ndir=f(dir,v[x][y]),nx=x+dx[ndir],ny=y+dy[ndir],nd=d;
		if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&dis[nx][ny][ndir]>nd)
			dis[nx][ny][ndir]=nd,q.push_front({nx,ny,ndir,nd});
		for(auto C:{'A','B','C'}) if(v[x][y]!=C){
			ndir=f(dir,C),nx=x+dx[ndir],ny=y+dy[ndir],nd=d+1;
			if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&dis[nx][ny][ndir]>nd)
				dis[nx][ny][ndir]=nd,q.push_back({nx,ny,ndir,nd});	
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;cin>>t;
	while(t--) solve();
}

O(1) 儒略日 p7075

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
std::array<i64, 3> date(i64 J){
    i64 offset, cycle, Z, A;
    if (J >= 2299161){
        offset = -((J - 2299161) / 146097);
        cycle = 400;
        Z = J + 146097 * offset;
        i64 alpha = (4 * Z - 7468865) / 146097;
        A = Z + 1 + alpha - alpha / 4;
    }else{
        offset = (2299160 - J) / 1461;
        cycle = 4;
        Z = J + 1461 * offset;
        A = Z;
    }
    i64 B = A + 1524;
    i64 C = 2 * (10 * B - 1221) / 7305;
    i64 D = 1461 * C / 4;
    i64 E = 10000 * (B - D) / 306001;
    i64 day, month, year;
    day = B - D - 306001 * E / 10000;
    if (E < 14){
        month = E - 1;
    }else{
        month = E - 13;
    }
    if (month > 2){
        year = C - 4716 - cycle * offset;
    }else{
        year = C - 4715 - cycle * offset;
    }
    return {year, month, day};
}
void solve(){
    i64 r;
    std::cin >> r;
    auto [year, month, day] = date(r);
    if (year <= 0){
        std::cout << day << " " << month << " " << (-year + 1) << " BC\n";
    }else{
        std::cout << day << " " << month << " " << year << "\n";
    }
}