❌

普通视图

发现新文章，点击刷新页面。
昨天以前Rei's Blog

XiaomiEU 固件添加国行 NFC

✇Rei's Blog
2025年12月12日 20:50

近期将手机从 AfterlifeOS 这一类原生刷回了 HyperOS3, 小米14 的类原生还是不够完善

不过国行版本的 HyperOS 不超过三天就让我想把手机摔了, 因此刷了基于国行固件的魔改版本 XIAOMI.EU

但是刷完之后, 国行的 NFC 功能用不了, 我的车钥匙/门卡/交通卡可还依赖这玩意呢

找了一下还没有适配当前版本的 Kernel SU 模块, 于是自己解包做了一个

解包国行系统包

先下载国行包并解压

1
2

wget https://bkt-sgp-miui-ota-update-alisgp.oss-ap-southeast-1.aliyuncs.com/OS3.0.5.0.WNCCNXM/houji-ota_full-OS3.0.5.0.WNCCNXM-user-16.0-306ce971bf.zip
unzip houji-ota_full-OS3.0.5.0.WNCCNXM-user-16.0-306ce971bf.zip payload.bin

现在的安卓刷机包大多会打成 payload.bin 这种包格式, 需要先解包

1
2
3
4

wget https://github.com/ssut/payload-dumper-go/releases/download/1.3.0/payload-dumper-go_1.3.0_linux_amd64.tar.gz
tar -xvf payload-dumper-go_1.3.0_linux_amd64.tar.gz
chmod +x payload-dumper-go
./payload-dumper-go -o ./ ./payload.bin

查看文件尺寸, 最大的是这个 product.img 用 file 指令查看后可以知道这是个 erofs 的单分区镜像包, 我们将其挂载

1
2
3

pacman -S erofs-utils erofsfuse
mkdir product
mount -t erofs -o loop product.img product

然后在挂载镜像的 app 目录下找到 MINextpay MITSMClient UPTsmService 三个必要组件, 将其打包成一个最简的 KernelSU module 刷入即可, 也就是只有 system/app/组件 和 module.prop 文件的最简包

1
2
3
4

cp -a ./product/app/MINextpay ./module/system/app/MINextpay
cp -a ./product/app/MITSMClient ./module/system/app/MITSMClient
cp -a ./product/app/UPTsmService ./module/system/app/UPTsmService
cp -a ./product/app/MIUISuperMarket ./module/system/app/MIUISuperMarket

为了方便后续更新版本, 做了个 Github Action 用来打包

其中奇怪的一点是, 在 Action 中使用 mount -t erofs -o loop product.img product 挂载镜像后 拷贝之后, 执行到 cp 这一步的时候会报

挂载

Github Action 报错

看上去是内存超限了的样子

因此换成了 fsck.erofs product.img --extract=product 指令将镜像中的文件提取出来

最后成品可以在 https://github.com/ReiAccept/MiPay4XiaomiEU 中找到

ICPC 2020 Shenyang

✇Rei's Blog
2021年9月6日 20:35
Featured image of post ICPC 2020 Shenyang

CF Gym : Dashboard - The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces

D Journey to Un’Goro 

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds; //If using pbds don't using std!
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF
const int MAXN=(int)3e5+3;

inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
inline int read(){int s=0,w=1;char ch=nc();while(!isdigit(ch)){if(ch=='-')w=-1;ch=nc();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=nc();} return s*w;}
//inline void read(int &x){char ch=nc();x=0;while (!(ch>='0'&&ch<='9')) ch=nc();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=nc();}//根据参数个数自动选择
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n,cnt;
char s[MAXN];

void dfs(int now, int ji, int ou, bool flag)
{
    if(cnt==100) exit(0);
    if(n%2)
    {
        if(ji+(n-ji-ou) < (n>>1) || ou + (n-ji-ou) < (n>>1) || ji > (n>>1)+1 || ou > (n>>1)+1) return;
    }
    else
    {
        if(ji+(n-ji-ou) < (n>>1) || ou + (n-ji-ou) < (n>>1) || ji > (n>>1) || ou > (n>>1)) return;
    }
    if(now == n)
    {
        for(int i=1;i<=n-1;i++) printf("%c",s[i]);
        printf("\n");
        cnt++;
        return;
    }
    s[now]='b';
    if(flag) dfs(now+1,ji+1,ou,flag);
    else dfs(now+1,ji,ou+1,flag);
    s[now]='r'; //flag取反
    if(!flag) dfs(now+1,ji+1,ou,!flag);
    else dfs(now+1,ji,ou+1,!flag);
}

inline void work()
{
    n=read()+1; ll ans=((ll)n/2) * ((ll)n-(ll)n/2);
    printf("%lld\n",ans);
    dfs(1,0,1,false);
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;//(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        //while(cin>>n) work(n);
        work();
    }
    return 0;
}
//构造一个长度为 n 的只含有 b,r 的字符串,使得子串中 r 数量为奇数的最多
//r 看成 1,b 看成 0 的话,前缀和中为奇数的子串就满足要求

F Kobolds and Catacombs 

 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
45
46
47
48
49
50
51
52
53
54
55

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds; //If using pbds don't using std!
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF
const int MAXN=(int)1e6+3;

inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
inline int read(){int s=0,w=1;char ch=nc();while(!isdigit(ch)){if(ch=='-')w=-1;ch=nc();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=nc();} return s*w;}
//inline void read(int &x){char ch=nc();x=0;while (!(ch>='0'&&ch<='9')) ch=nc();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=nc();}//根据参数个数自动选择
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;
int a[MAXN],b[MAXN];

inline void work()
{
    n=read();
    for(int i=1;i<=n;i++) b[i]=a[i]=read();
    sort(b+1,b+1+n,[](int x,int y){return y>x;});
    //for(int i=1;i<=n;i++) printf("%d ",b[i]);
    int cura=0,curb=0,ans=0;
    for(int i=n;i>=1;i--)
    {
        cura+=a[i]; curb+=b[i];
        if(cura==curb) ans++;
    }
    printf("%d\n",ans);
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;//(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        //while(cin>>n) work(n);
        work();
    }
    return 0;
}

G The Witchwood 

 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
45
46
47
48
49
50

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds; //If using pbds don't using std!
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF
const int MAXN=(int)1e3+3;

inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
inline int read(){int s=0,w=1;char ch=nc();while(!isdigit(ch)){if(ch=='-')w=-1;ch=nc();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=nc();} return s*w;}
//inline void read(int &x){char ch=nc();x=0;while (!(ch>='0'&&ch<='9')) ch=nc();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=nc();}//根据参数个数自动选择
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n,k;
int a[MAXN];

inline void work()
{
    n=read(); k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n,[](int x,int y){return y<x;});
    int ans=0;
    for(int i=1;i<=k;i++) ans+=a[i];
    printf("%lld\n",ans);
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;//(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        //while(cin>>n) work(n);
        work();
    }
    return 0;
}

I Rise of Shadows 

 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
45
46
47
48
49
50

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds; //If using pbds don't using std!
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF
const int MAXN=(int)1e5+3;

inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
inline int read(){int s=0,w=1;char ch=nc();while(!isdigit(ch)){if(ch=='-')w=-1;ch=nc();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=nc();} return s*w;}
//inline void read(int &x){char ch=nc();x=0;while (!(ch>='0'&&ch<='9')) ch=nc();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=nc();}//根据参数个数自动选择
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int h,m,a;

inline void work()
{
    h=read();m=read();a=read();
    if(a == h*m/2) printf("%lld\n",h*m);
    else
    {
        int g=__gcd(h-1,m);
        printf("%lld\n",g*(((a/g)<<1)|1));
    }
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;//(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        //while(cin>>n) work(n);
        work();
    }
    return 0;
}

K Scholomance Academy 

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include<bits/stdc++.h>
#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF
const int MAXN=(int)1e6+3;

//int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

struct Node
{
    bool c;
    int s;
}a[MAXN];

int n,tpfn,tnfp;

void work()
{
    //scanf("%d",&n);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char c; //scanf("%c %d",c,&a[i].s);
        cin>>c>>a[i].s;
        a[i].c=(c=='+');
        //printf("111");
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i].c) tpfn++;
        else tnfp++;
    }
    sort(a+1,a+1+n,[](Node a,Node b){
        if(a.s == b.s){
            if(b.c) return false;
            if(a.c) return true;
        }
        return a.s<b.s;
    });
    int tp=tpfn,fp=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].c) tp--;
        else cnt+=tp;
    }
    rld ans=(rld)cnt / (tpfn*tnfp);
    printf("%.9LF\n",ans);
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;//(int)read();
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        //while(cin>>n)
        work();
    }
    return 0;
}

ICPC 2020 Jinan A Matrix Equation

✇Rei's Blog
2020年12月31日 20:43

这个题算是个翻车题，做出来可以铁翻银的，燃鹅翻车在这个题上了

证明

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define MMST(x,y) memset(x,y,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;
const int MOD=998244353;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n,ans=1;
int a[203][203],b[203][203];
bitset<203> bit[203];

void insert(bitset<203> x)
{
    for(int i=1;i<=n;i++)
        if (x[i]) 
        {
            if(!bit[i].count()) 
            {
                bit[i]=x;
                break;
            }
            x^=bit[i];
        }
}

void work()
{
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>b[i][j];
    for(int t=1;t<=n;t++)
    {
        for(int i=1;i<=n;i++) bit[i]=0;
        for(int i=1;i<=n;i++)
        {
            bitset<203> x=0;
            for(int j=1;j<=n;j++) x[j]=a[i][j];
            x[i]=x[i]^b[i][t];
            insert(x);
        }
        for(int i=1;i<=n;i++)if(!bit[i].count()) ans=(ans<<1)%MOD;
    }
    cout<<ans<<endl;
    return;
}

signed main()
{
    int T=1;//read();
	for(int Case=1;Case<=T;Case++)
    {
        //printf("Case #%d: ",Case);
        work();
    }
    return 0;
}

ICPC 2020 Shangahi

✇Rei's Blog
2020年12月13日 20:57

嘛，没想到我的ICPC之旅的第一站就那么卷,开局南师大6S AC最速传说，然后被dq了，开场签到很稳，和文哥直接推出了公式，和黄总写的暴力程序直接对拍正确A掉签到题

然后在开B和M之间纠结，队伍里就我用过git，就看懂了M的题意，然后和黄总一起构树两次DFS写M，文哥没用过git就没看懂git的忽略操作的意思，文哥去开了B，然后M构树挂了三四次浪费了4H，然后文哥来看了M，这次告诉文哥，git的忽略在这题就理解成删除，文哥上手M题，直接30MIN给过了，文哥·工大唯一真神。到这里已经来不及做B了，实际上文哥B的思路是正确的。

感觉这场我有点演==挂件模式全开，我的构树是竞赛少用的指针+vector构树，然后和黄总的构树代码完全不兼容，后来想到了Trie，但是用的模板好像是假的==

B 

 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

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3+3;
int cnt,n,m;
char a[maxn][maxn] ,b[maxn][maxn];
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++)scanf("%s",a+i);
	for(int i=0;i<n;i++)scanf("%s",b+i);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(a[i][j]!=b[i][j]) cnt++;
	if(cnt>n*m/2)
    {
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(a[i][j]=='.') a[i][j]='X';
				else a[i][j]='.';
	}
	for(int i=0;i<n;i++) printf("%s\n",a+i);
	return 0;
}

D 

 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

#include<bits/stdc++.h>

using namespace std;

double n,p1,v1,p2,v2,l,r,mid;

double calc(double n,double p,double v)
{
    return min(n-p+n,p+n)/v;
}

void work()
{
    scanf("%lf%lf%lf%lf%lf",&n,&p1,&v1,&p2,&v2);
    double ans=min(calc(n,p1,v1),calc(n,p2,v2));
    if (p1>p2) swap(p1,p2),swap(v1,v2);
    ans=min(ans,max(p2/v2,(n-p1)/v1));
    l=p1,r=p2;
    for (int i=1; i<=100; i++)
    {
        mid=(l+r)/2.0;
        double ans1=calc(mid,p1,v1),ans2=calc(n-mid,p2-mid,v2);
        ans=min(ans,max(ans1,ans2));
        if (ans1>ans2) r=mid;
        else l=mid;
    }
    printf("%.10lf\n",ans);
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)work();
}

G 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5+100;

signed main()
{
	int n;
	scanf("%lld",&n);
	int ans=(n-(n/3))*(n/3)+(n/3)*(n/3-1)/2;
	cout<<ans<<endl;
	return 0;
}

I 

 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

#include<bits/stdc++.h>
#define MN 500

using namespace std;

typedef long double ld;
const ld pai = acos(-1);

int n,m;

ld len,ans;
ld f[MN+5];

int main()
{
	scanf("%d%d",&n,&m);
	ld d = pai/m; 
	for(int i=1;i<m;i++)
    {
		if(i*d>2)len+=2;
		else len+=i*d;
	}
	len*=2;
	len+=2;
	for(int i=1;i<=n;i++)
    {
		f[i]=len*i+2*m*(i-1)+1+f[i-1];
		ans += m*(f[i]*2-i*len);
	}
    if(m==1) ans-=(2+2*n)*n/2;
	printf("%.10lf\n",(double)ans);
}

M 

  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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include<bits/stdc++.h>
using namespace std; 
int n,m;
int vis[10100];
int qian[10100];
int z[10100];
int shu[10100];
int vi[10100];
int o[10100];
void init(){
	memset(vis,0,sizeof(vis));
	memset(qian,0,sizeof(qian));
	memset(z,0,sizeof(z));
	memset(shu,0,sizeof(shu));
//	memset(vis,0,sizeof(vis));
	memset(vi,0,sizeof(vi));
	memset(o,0,sizeof(o));
}
struct node{
	int i;
	int x;
};
int main()
{
	int T ;
	cin>>T;
	while(T--){
		cin>>n>>m;
		init();
		map<string ,int > mp;
		int tot=1;
		for(int i=1;i<=n;i++){
			string str;
			cin>>str;
			str=str+"/";
			string s;
			int flag=0;
			string p;
			for(int j=0;j<str.size();j++){
				if(str[j]=='/'&&flag==0){
					flag=1;
					p=s;
					if(mp[s]==0){
						mp[s]=++tot;
						qian[tot]=1;
						z[tot]=1;
					}
				}
				else if(str[j]=='/'&&flag==1){
					if(mp[s]==0){
						mp[s]=++tot;
						qian[tot]=mp[p];
						z[tot]=1;
						shu[mp[p]]++;
					}
					p=s;
				}
				s+=str[j];
			}	
		}
		for(int i=1;i<=m;i++){
			string str;
			cin>>str;
			str=str+"/";
			string s;
			int flag=0;
			string p;
			for(int j=0;j<str.size();j++){
				if(str[j]=='/'&&flag==0){
					flag=1;
					p=s;
					if(mp[s]==0){
						mp[s]=++tot;
						qian[tot]=1;
						z[tot]=0;
					}
				}
				else if(str[j]=='/'&&flag==1){
					if(mp[s]==0){
						mp[s]=++tot;
						qian[tot]=mp[p];
						z[tot]=0;
						shu[mp[p]]++;
					}
					p=s;
				}
				s+=str[j];
			}	
		}
//		for(int i=1;i<=tot;i++){
//			cout<<i<<" ";
//		}
//		cout<<endl;
//		for(int i=1;i<=tot;i++){
//			cout<<qian[i]<<" ";
//		}
//		cout<<endl;
//		for(int i=1;i<=tot;i++){
//			cout<<shu[i]<<" ";
//		}
//		cout<<endl;
		queue<node> p;
		int ans=0;
		for(int i=2;i<=tot;i++){
			if(shu[i]==0){
				if(z[i]==1) {
					ans++;	p.push(node{i,z[i]});
				}
			
			}
		}
//		cout<<p.size()<<endl;
//		cout<<ans<<endl;
		while(!p.empty()){
			node t=p.front();
			p.pop();
			vi[qian[t.i]]++;
//			o[qian[t.i]]+=t.x;
//			cout<<t.i<<" "<<t.x<<endl;
			if(vi[qian[t.i]]==shu[qian[t.i]]&&qian[t.i]!=1){
				ans-=shu[qian[t.i]];
				ans++;
				p.push(node{qian[t.i],0});
			}
		}
		cout<<ans<<endl;
	}
}

银欣 CS382

✇Rei's Blog
2025年4月6日 05:36
Featured image of post 银欣 CS382

为什么要更换机箱

INWIN 的 MS04 作为 NAS 机箱在我这服役多年，承载了 凄惨红H61 + i5-3470 和 华擎H97M-ITX/ac + E3-1265Lv3 两代硬件，当我这几天想给他升级 B760I + i3-12100 时，机箱的原装电源终于是吃不太消，来自 1U 电源风扇轴承的声音到达了一个让人难以忍受的程度。

为了拯救这个老机器，我还尝试购买了一下海韵的 350M1U 电源更换上去，当时看中的是海韵的 50% 以下电源负载时风扇停转功能。但是这个电源，在 MS04 这个箱子里的散热有点问题，导致虽然时低负载情况下，依旧会在开启一段时间后积热，然后风扇开始转动，海韵给这个电源配备了恐怖的万转风扇，这个风扇在这种情况下并未全速运行，但是依旧有令人讨厌的声音。

还有一点就是，原机上是 4*14T 的 WD HC530 硬盘，其实也有点不够用

终于，在清明节晚上大半夜，我决定是时候光荣退役这台 MS04，换个新的 8 盘位 NAS 机箱。

机箱选型

考虑过以下几个机箱选型

迎广 MS08

那么大一个箱子，明明不缺空间，用的却是 1U 电源，排除

银欣 DS380

虽然是个8盘位箱子，但是硬件兼容性还是小机器那套，排除，不过体积确实小

宝藏盒 Pro

小作坊的定制产品，我还挺喜欢，用的曙光的金属盘架，不过非常贵，1399，排除

银欣 CS380

发布有些年头了，兼容 ATX 主板，塑料盘架，黄鱼400块，京东700块

银欣 CS382

最终选用了这款，兼容 mATX 主板，塑料盘架，京东899，单纯觉得看着比 CS380 顺眼就买了。

电源

电源没啥好说的，海韵和振华的十年质保系列看哪个便宜买哪个就好了。不过离谱的是，刚好赶上振华打折，750W比650W便宜，那就买个750W好了（不过说到底，这套配置哪怕硬盘插满可能连 200W 都到不了吧）

电源包装

电源开箱

顺带说一下振华的新版电源，之前买HG850的时候，他的模组线有送个布袋，但是现在这个新版750W没了，不过附带的新版模组线，比以前的线软了很多很多，好插多了。

装机

很普通的装机，看我博客的人应该不需要看装机过程，很好装的机箱

B760M 刀锋钛

MSI B760M 刀锋钛 这张主板自带 6SATA，把芯片组自带的 SATA 接口全部引出。并且选择 MSI 的主板有个好处, BIOS 里面就可以直接把 RGB 灯光彻底关闭

值得说的一点就是，硬盘笼上的 SATA/SAS 接口是不兼容右向弯头线材的

SATA线材冲突

以及盘架是类似群晖那种，我并不喜欢，建议直接兼容戴尔的服务器盘架算了，不过相比群晖，给了一个螺丝孔加固

盘架

DELL 的 H730 卡在更新最新的固件之后可以直接在 BIOS 里面更改为 HBA 卡模式, TrueNAS 推荐使用 HBA 卡模式, 由 ZFS 直接控制硬盘, 如果是 OMV 之类或者其他 btrfs 的系统, 这里还是建议打开硬件 RAID

不过说实话之前那台 NAS 虽然用的是 TrueNAS 但是其用了 Intel RAID, 然后在 ZFS 里面直接选择条带模式。

其实用更便宜的 DELL H330 HBA 卡就行了, 用 H730 主要是因为这张卡现在可以设置为, 在非 RAID 模式下也使用 DDR Cache

DELL PERC9 H730

用 storcli 查看, H730 工作在 HBA 模式下的温度只有 42 度

机箱前面板，我到手才知道，这个箱子不仅有一个标准的光驱位，还有个超薄光驱位

前面板

和MS04的合照

和H5 Flow的合照

UPS

由于我现在住的公寓非常逆天，电费没了之后，不会给任何提示就断电，所以一台 UPS 还是很有必要的，地铁一小时按群友价去收了一台全新的 APC BK650M2-CH

UPS

在 TrueNAS 中选好驱动即可使用

TrueNAS UPS Config

装完后剩余槽位与后续改进

  1. 3.5盘位 1 个, 该盘位为内置盘位，没有背板，用SATA线直接连接
  2. 薄光驱位 1 个, 考虑后续真的放个光驱进去
  3. 厚光驱位 1 个, 考虑后面买个热插拔 2.5 硬盘拓展笼子或者 E1.S 笼子
  4. 2.5英寸盘位 2 个, 来点 U2 大船
  5. 主板，迟早要把这个 ITX 板子卖了换个大板子

附录

配件价格表

类型 名称 数量 来源 总价(CNY)
机箱 银欣 CS382 1 京东 899
电源 振华 LEADEX III GOLD 750W 1 京东 659
机械硬盘 WD HC530 4 上台NAS继承 0
机械硬盘 东芝 MG08 4 淘宝 3356
M2 SSD (Cache) PM981a 1T 1 上台NAS继承 0
M2 SSD (OS) SN750 500G 1 上台NAS继承 0
RAID 卡 DELL H730 1 咸鱼 279
SAS 线 安费诺一分四服务器拆机 2 咸鱼 38.8
主板 MSI B760M 刀锋钛 1 闲鱼 719
CPU i3 12100 1 黄鱼 499
内存 阿斯加特 16G 7000Mhz DDR5 2 上台NAS继承 0
散热器 AXP90x53 1 上台NAS继承 0
网卡 华为 SP310 1 上台NAS继承 0
UPS APC BK650M2-CH 1 杭州本地群友 299
总价 6748.8

MikroTik RB5009

✇Rei's Blog
2023年7月30日 10:30
Featured image of post MikroTik RB5009

在 Путин, Владимир Владимирович 搞事之前，RB5009 的价格一直是 12xx 软妹币……

然后……然后……这玩意就成理财产品了……

观望了好几年，这玩意的价格从 12xx -> 2xxx -> 13xx 虽然价格还是很高，但是还算可以接受

不过一个 10G SFP+ 一个 2.5G RJ45，剩下 7 个都是 1000M 口这种配置，MikroTik做出来属实有些膈应人了……

哦，背板带宽还跑不满

不过主要是 E3-1265Lv3 软路由实在是撑不起家里的网络了，不得不换一个

包装盒

顶面

正面

目前杭州租的房子里机架还没搞好，只能丢个袋子里挂起来，灵车的很

等下次回台州把猫棒什么都拿来，淘汰掉联通的垃圾光猫

Tips: 如果您要将 RB5009 与 RTL960x 系列 SFP 猫棒协商 2.5G 速率

首先需要 SSH到猫棒上执行 flash set LAN_SDS_MODE 6 然后回到 winbox，关闭自动协商，设置速率为 2.5G baseX，然后需要等待第一次重协商的时间会比较长，参考资料

方程豹 钛7

✇Rei's Blog
2025年12月3日 23:09
Featured image of post 方程豹 钛7

换车与选车

从 2019 年高中毕业拿到驾照到我工作两年，我开的车一直是家里的 Audi A6L 55TFSI Quattro 车型，说实话我相当喜欢这辆车，底盘稳定可靠，动力跟脚，机械结构上除了发动机烧机油外没见过啥问题，让我信心十足的度过了我的新手驾驶期。

不过工作两年后，我需要在杭州买一辆车，需要满足以下条件

  1. 品牌无所谓，家里一直开的是BBA，我自己没啥情怀
  2. 某方面的技术领先（这点其实淘汰了日系，只留下了德系（发动机/底盘技术领先）和国产车（三电技术领先））
  3. 买起来比较简单……别那种换电租电什么方案一堆的
  4. 我自己的现金流支持全款买

算了一下自己可以拿出来的流动资金，最开始的换车计划选了以下三台车（当然我实际上不止试驾了三台）

  • Xiaomi YU7 Pro
  • Tesla Model Y
  • Audi Q6L

一些试驾与感受

Xiaomi YU7 Pro

好开，好车，我各个方面都很喜欢，但是提车要38周，遂放弃

如果不是提车慢，这篇文章就是小米YU7了

Tesla Model Y

好开，底盘稳，动力强，操控灵

但是我不好说这是不是一辆好车

作为一个一直坐家中BBA传统油车长大的人，我认为，车内座舱的体验也是驾车很重要的一部分，特斯拉的内饰真不太行

老生常谈的 屏幕换档 方向盘按键转向灯 也是我觉得难受的地方

Audi E5

不错，但是没有四个圈不好看

Audi Q6L

油改电真不行吧

焕新极氪7X

全车电动门很棒, 车机大屏和很棒, 整车加速, 操控都不错, 还有空气悬挂, 就是后排空间可能有点小

那这车那么好, 为什么不买呢？

家里人听说是吉利车：吉利车，天～窗～漏～水～啦～

哈哈，台州人对吉利的刻板印象来了

不过认真的说，吉利车不差，油的部分比BYD好，我觉得是无可争议的国产第一，底盘调教在国产车中也十分优秀, 但是电的部分确实比不上BYD

方程豹钛7

说起来我最开始不认识这个牌子，但是滨江展厅开在吉利店边上，路过的时候看到里面摆了一辆钛7，外观看上去很霸气，于是加了销售的微信，预约了第二天的试驾。

试驾后的体验确实还可以，问了一下知道是BYD的车

BYD的车到还有个好处，车机开adb折腾方便

福特智趣烈马（云）

这个车处于发布但是没有开售，不过我还挺喜欢的，所以在这里云一下

BRONCO 作为美系车驾驶方面不会差

但是他是个增程车，高速油耗比插混高（废话，你都买美系了还在意油耗？）

越野方面作为老牌美系车，给的比钛7多，还给了个全尺寸备胎

从已发布的信息上看是个好车但是还在预售中，买不到也试不到

确定购买与提车

说实话，试完之后感觉方盒子车真的视野好，且空间大更舒适，所以于 10.19下订, 11.04提车，相对于之前刚开始想的三台车（30W左右），实际上是省钱了哈哈

提车流程反正就那一套，方程豹的客餐还可以，不过橘子是酸酸的

主要是原先自己想要的三台车试驾后，都有些当时不可接受的问题，这个车正好还挺符合我各方面爱好和习惯的，而且比亚迪的三电技术也不错

1000KM 后

一千公里其实也没多少，开出去和朋友在钱塘江钓鱼玩玩之类的，然后从杭州开次高速回台州老家就差不多了。

底盘上，没有之前开A6L的信心足，跑一次高速就很明显能感受到，不过这两车也不在一个价位，这车二十来万，快一米九高，哪怕电池在车底带来天然的稳定性，和能买两台钛7的A6L对比确实有点欺负他了

动力上，不得不说这套插混系统真的是天才，太有力了兄弟，这也是电机系统领先于内燃机的地方

操控，灵活，好

RouterOSv7 泥头车与酒驾 BGP

✇Rei's Blog
2023年6月13日 17:14
Featured image of post RouterOSv7 泥头车与酒驾 BGP

安装

DD

MikroTik官方文档里推荐的安装方法是在Setting - Custom ISO - SystemRescue挂载镜像后操作，但是我懒，直接在 Debian 下 dd 的

1
2
3

wget https://download.mikrotik.com/routeros/7.9.2/chr-7.9.2.img.zip
unzip chr-7.9.2.img.zip
dd if=chr-7.9.2.img of=/dev/vda

这时候如果您是按照官方文档里推荐的安装方法安装的话，需要解除 ISO 挂载，机器会自动重启

修改用户 

1
2

/user add name=rei password=密码 group=full
/user remove admin

关闭不需要的服务

我只需要 SSH 和 winbox 服务

 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

[rei@MikroTik] > /ip service print
Flags: X, I - INVALID
Columns: NAME, PORT, CERTIFICATE, VRF
#   NAME     PORT  CERTIFICATE  VRF 
0   telnet     23               main
1   ftp        21                   
2   www        80               main
3   ssh        22               main
4 X www-ssl   443  none         main
5   api      8728               main
6   winbox   8291               main
7   api-ssl  8729  none         main
[rei@MikroTik] > /ip service set 0,1,2,4,5,7 disabled=yes
[rei@MikroTik] > /ip service print
Flags: X, I - INVALID
Columns: NAME, PORT, CERTIFICATE, VRF
#   NAME     PORT  CERTIFICATE  VRF 
0 X telnet     23               main
1 X ftp        21                   
2 X www        80               main
3   ssh        22               main
4 X www-ssl   443  none         main
5 X api      8728               main
6   winbox   8291               main
7 X api-ssl  8729  none         main

也许还可以改个SSH端口什么的

接下来在 winbox 下操作

配置 IPv6

直接 dd 安装 ROS 的 v4 是活的，但是 v6 寄了。在 IPv6 - Address 中添加地址

然后在 IPv6 - Settings 中取消勾选 IPv6 Forward 即可

最后 ping 一下 2001:4860:4860::8888 （GoogleDNS）验证是否通网

与 Vultr 建立 BGP Sessions

Filters

其实如果你和我一样单纯只是想在 Vultr 上收个全表的话，理论来说不用管这玩意。

以及酒后写 v7 的规则实在是容易出事，还是以后有机会再写吧

Templates

显然，整个模板可以让我们偷懒摸鱼，我是直接修改了自带的 default 模板

Connection

Vultr 上个人建议建立两个 Connection，也就是一个 v4 的和一个 v6 的

v4 的写法也差不多，照着改就行，其实就是把 Vultr 给你的 Bird 模板改改塞进去

然后切换到 BGP - Sessions 选项卡

开头的 E 代表 Established 也就是你配的没问题生效了

广播你自己的 IP

由于我买不起v4，所以这里只能写v6了

Firewall

首先在 IPv6 - Firewall - Address Lists 中新建一条你要播的地址

Output Network

然后在承载你这条网络所对应的 BGP Connection 中的 Filter - Output Network 中将其选中

Route

在 IPv6 - Route 中建立一条用于承载广播地址的路由

Address

最后就和第一步配v6网络的时候一样，在 IPv6 - Address 中添加地址即可

Incomplete certificate chain prevents ClashForAndroid from connecting to TLS proxies

✇Rei's Blog
2023年1月1日 04:18
Featured image of post Incomplete certificate chain prevents ClashForAndroid from connecting to TLS proxies

Over the past few days , ClashForAndroid could not connect TLS proxies. The reason was found in the log

1

x509: vertificate signed by unknown authority

And , This config.yaml works well on Windows/Arch Linux/macOS/iOS(Stash)

At first, I wondered if the RootCA of my certificate was not trusted by Android? But using Chrome/Edge to access the https page built with the same certificate shows that the certificate is trusted.

After asking a friend who is an Android developer, he said: “Since Android 7.0, third-party applications do not trust manually installed root certificates by default.”

However, this RootCA is not installed manually. It is ISRG Root X1 directly built into the system. (I use the certificate issued by Let’s Encrypt)

Then I saw an article that solved the problem: 如何补全 SSL 证书链？

通常情况下 PC 端浏览器都可以通过 Authority Info Access（权威信息访问）的 URL 链接获得中间证书，但在部分 Android 系统的浏览器上访问时会出现证书不可信或无法访问等问题。

主要原因在于部分 Android 系统的浏览器并不支持通过 Authority Info Access（权威信息访问）的 URL 链接获得中间证书，这时您需要把证书链文件按照 SSL 证书链的结构合并为一个文件重新部署到服务器上，浏览器在与服务器连接时将会下载用户证书和中间证书，使您的浏览器访问时显示为可信证书。

After using fullchain.cer , the proxies can connect normally. Chrome/Edge on Android can visit website with intermediate certificate because it has built-in “Authority Info Access” capabilities.

Tips: In some versions of OpenWRT, it is also not supported to automatically download and complete intermediate certificates through “Authority Info Access”.

UFI001C (杂牌4G 随身 WIFI)

✇Rei's Blog
2022年6月11日 12:43
Featured image of post UFI001C (杂牌4G 随身 WIFI)

上次折腾随身WIFI还是高中的时候的阿尔卡特Y855 不得不说那玩意的性能可比这破棒子强多了，2GB RAM，4GB eMMC，支持SD卡，高通MDM9225基带，3000mAh电池，最关键的是，SSH是直接开放的(root@192.168.1.1，密码oelinux123)

这次这个主要是看见灵车手痒了，折腾完了才想起自己的电脑好像是有WWAN模块的……

备份

这里其实没啥值得说的，但是有一点就是我的电脑原来就装了小米的9008驱动，但是这个驱动莫名其妙搜不到设备

更换驱动

在这里选中2.1.22版本驱动即可正常的全量备份

耗时约5分钟

刷全网通与切卡

原来我是准备直接刷OpenWRT或者Debian的，但是我插了自己卡（联通）工作不正常，所以想着直接把全网通基带也刷了算了

刷基带（备份基带）一种是有root权限，直接用酷安各类教程里写的“星海SVIP”（其实我觉得这软件难用的EB）

1
2
3
4

adb reboot bootloader
# 然后你需要一个 Magisk 打过 Patch 的 boot.img
fastboot flash boot boot_patched.img
fastboot reboot

接着“星海SVIP”里点“高通强开1”，接着备份和刷入

还有一种就是直接用QPST的备份.xqcn功能

刷完全网通之后的连接还是不正常，此时切卡后的界面是这样的

待续

写到这里突然发现我有个大作业快DDL了……

NECPC 2022 (第16届CCPC东北四省赛)

✇Rei's Blog
2022年6月1日 15:42
Featured image of post NECPC 2022 (第16届CCPC东北四省赛)

校内选拔

其实可以直接要个名额打，但是还是打了一下实验室的选拔，然后发现题用的是NECPC2020 的这也就是我为啥2022年写了NECPC2020的博客

然后单打手速没组队的快校内RANK2

训练

我和yz的训练……那一定是没有的，长春封了那么多天，一直在学考研和摸鱼，考研已经上岸的文哥在写毕设和自己一个人练

赛前我唯一的训练应该就是打了Codeforces Round #789 (Div. 2)

Codeforces Round #789 (Div. 2)

疫情

这次NECPC不得不说疫情了，首次体验异地三人三机

不过长春封了那么多天，我反正已经麻了，没啥说的了

但是对于打比赛来说，异地打沟通是真的麻烦，就像是写个公式，线下我可以直接写草稿纸，线上我只能腾讯会议共享屏幕然后VSCode开个md打公式然后预览

过程

签到丝滑的一比

然后文哥的BFS写炸了，我类似记搜的一个东西也炸了，调试调麻了，摸了

看了下B.Capital Program 是个傻逼题就干过去了

然后嘛，然后我们三个人就打出了各自在NECPC的最差成绩铜哈哈

我记得我大二刚开始打ACM的时候，打星单挑NECPC2020也有银尾的样子

不过好像嘻嘻哈哈的，大家打的也挺欢乐（

反正没有任何训练，既然做好了摸鱼的准备的话，开心最重要qwq

魔改华为 MA5671A 和 Nokia G-010S-A

✇Rei's Blog
2021年12月27日 00:05
Featured image of post 魔改华为 MA5671A 和 Nokia G-010S-A

2021-12-27 更新

这玩意现在在国内论坛已经烂大街了

事情的起因是因为上学期结束暑假回家的时候，移动给小区的用户设备升级，然后给我家的设备换成了菊花的 HS8145V5，虽然这款设备本身的性能没什么好黑的，比之前的光猫强多了，但是这玩意在我的弱电箱内占了很大一块地方让我很不爽来着，而且 WLAN SSID 强制带 CMCC

最无话可说的是，移动的人把我原来的软路由和AP直接拆了，麻了

暑假的时候训练，camp，帮孙老师上课（实际上大头是摸鱼）这一套下来都没空搞家里的网络，就一直咕到了寒假

然后给我有两个选择就是

  1. 低成本方案：把华为的光猫刷回原版固件改桥接接入软路由，然后继续用（毕竟这玩意性能还凑合）
  2. 硬件更换方案：换掉华为的光猫，直接在软路由上整 PON Stick，可以节约弱电箱的空间

最后还是选了方案2，HS8145V5 最大的问题是热。。虽然性能完全达标，但是真的很热，并且多一个设备让我的走线强迫症发作了

因此在瞎翻 OpenWRT 论坛和大黄鱼之后发现了神奇的洋垃圾模块 华为 MA5671A 和 Nokia G-010S-A （还有一个 G-010S-P）

于是脑子一热下单 Intel 82599 和一个拆机的 G-010S-A

为什么说是脑子一热呢

这个东西。。。完全不能在中文网站上搜到相关结果

并且没有提供 Datasheet ，Google 能找到相关资料的地方只有

Will GPON Nokia G-010S-A change sn? - Hardware Questions and Recommendations - OpenWrt Forum

Nokia G-010S-A Pin 6 Issue (rsaxvc.net)

hwti/G-010S-A: All about Nokia G-010S-A GPON SFP (github.com)

并且买完才发现 G-010S-A 用的光缆是 APC （斜切，外观为绿色端子）（顺带一提，MA5671A 也是 APC）

而我家的入户光纤是 UPC （平切，外观为蓝色端子）的，靠谱起见大概我还需要去借一台熔纤机或者买个转接光纤这样

以及还有个坑点是，G-010S-A，G-010S-P，MA5671A 支持到2.5Gpbs 的 GPON，但是 Intel 82599 只提供 1Gpbs/10Gpbs 两种速率选择，也就是说，只能工作在1Gpbs上，但是这个价格捡垃圾没有其他选择了（

然后嘛……就是等待31号飞机飞回家里装咯，过两天再更新

其实折腾好了，但是我摸了，就咕了qwq

2022年的Update，你们以为我咕了，但是实际上我没咕，这何尝也是不是一种咕捏

G-010S-A 这个猫棒，要按照上面给出的 Nokia G-010S-A Pin 6 Issue (rsaxvc.net) 这篇里面进行一个改造，才能兼容我的 Intel X520-DA2 网卡，改完之后是这样的

然后……然后就直接按 hwti/G-010S-A 上直接配好 SN 和 Password 就行了，家里宽带光猫装机的时候我直接问师傅要了全部接入数据，也就没有破解光猫这种问题了捏

至于华为 MA5671A 捏，不知道啥时候想写，这个就是要自己找个OP固件，拿 Flash 编程器刷进去就好了，稍微复杂一些，但是也很简单

MA5671A和G-010S-A其实是同方案的产品，但是固件不通用，有些小细节不同，MA5671A不用物理魔改电路这样

UPC和APC光纤的问题我最后是五块钱一条无源光转换线解决的

Codeforces Round #715 (Div. 2)

✇Rei's Blog
2021年4月17日 17:05
Featured image of post Codeforces Round #715 (Div. 2)

A - Average Height 

 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

#include<bits/stdc++.h>
//#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF

int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;
int a[10000];

void work()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++) if(a[i]%2)printf("%d ",a[i]);
    for(int i=1;i<=n;i++) if(a[i]%2==0)printf("%d ",a[i]);
    printf("\n");
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=read();
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        work();
    }
    return 0;
}

B - TMT Document 

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include<bits/stdc++.h>
//#define int long long//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF

int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;
string s;

void work()
{
    cin>>n>>s;int mx=0;
    stack<char> st;
    for(int i=0;i<(int)s.size();i++)
    {
        if(s[i]=='T')
        {
            st.push('T');
        }
        if(s[i]=='M' )
        {
            mx++;
            if(!st.empty())
            {
                st.pop();
            }
            else
            {
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    while(mx--)st.pop();
    if(!st.empty())
    {
        cout<<"NO"<<endl;
        return;
    }
    for(int i=(int)s.size()-1;i>=0;i--)
    {
        if(s[i]=='T')
        {
            st.push('T');
        }
        if(s[i]=='M' )
        {
            mx++;
            if(!st.empty())
            {
                st.pop();
            }
            else
            {
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<"YES"<<endl;
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T;cin>>T;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        work();
    }
    return 0;
}

C - The Sports Festival 

 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//__int128
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF

int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

void work()
{
    int n=read();
    vector<int> a(n);
    for (int i=0;i<n;i++)a[i]=read();
    sort(a.begin(), a.end());
    vector<vector<int> > dp(n, vector<int>(n));
    for (int d=1;d<n;d++)
        for (int i=0;i+d<n;i++)
            dp[i][i+d]=min(dp[i][i+d-1],dp[i+1][i+d])+a[i+d]-a[i];
    cout<<dp[0][n-1]<<endl;
    return;
}

signed main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=1;
    for(signed Case=1; Case<=T; Case++)
    {
        //printf("Case %d: ",Case);
        work();
    }
    return 0;
}

D - Binary Literature 

 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

#include <bits/stdc++.h>
using namespace std;
int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}
int n;
int a[3][501009];

string buildx(int x,int y,int cxx)
{
    string tmp1=""; int ptr=1;
    for(int i = 1; i <= 2 * n; i++)
        if(a[y][i] == cxx)
        {
            while(ptr <= 2 * n && a[x][ptr] != a[y][i]) tmp1 += a[x][ptr++] ? "1" : "0";
            tmp1 += a[y][i] ? "1" : "0";
            ptr++;
        }
        else tmp1 += a[y][i] ? "1" : "0";
    while(ptr <= 2 * n) tmp1 += a[x][ptr++] ? "1" : "0";
    return tmp1; 
}
string build(int x, int y)
{
    string tmp1 =buildx(x,y,0),tmp2 =buildx(x,y,1);
    if(tmp1.size() < tmp2.size()) return tmp1;
    else return tmp2;
}
void work()
{
    n = read();
    for(int j = 0; j < 3; j++)
        for(int i = 1; i <= 2 * n; i++)
            scanf("%1d", &a[j][i]);
    string t1 = build(0, 1),t2 = build(0, 2),t3 = build(1, 2);
    if(t3.size() < t2.size()) swap(t3, t2);
    if(t2.size() < t1.size()) swap(t2, t1);
    cout << t1 << endl;
}
signed main()
{
    int Case = read();
    while(Case--) work();
    return 0;
}

E - Almost Sorted 

 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
45
46
47

#include <bits/stdc++.h>
#define int long long
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) emplace_back(x)
#define mkp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double rld;
typedef unsigned long long ull;

const rld eps = 1e-6;
const int INF=0x3f3f3f3f;//0x3f3f3f3f3f3f3f3f;//LLINF

int read(){int s=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return s*w;}

int n,k;
int a[100003];

void work()
{
    n=read();k=read()-1;
    if (n <= 61 && (int)1<<(n-1) <=k)
    {
        printf("-1\n");
        return;
    }
    iota(a+1, a+n+1, 1);
    for (int i=60,j;i>=0;i=j)
    {
        j = i-1;
        if (~(k>>i)&((int)1)) continue;
        while (j >= 0 && ((k>>j)&1))j--;
        reverse(a+n-1-i, a+n-j);
    }
    for (int i=1;i<=n;i++) printf("%lld%c",a[i]," \n"[i==n]);
    return;
}

signed main()
{
    int T=read();
    while(T--)work();
    return 0;
}

附中OJ从魔改HUSTOJ切换到Hydro啦！

✇Rei's Blog
2021年3月6日 20:36
Featured image of post 附中OJ从魔改HUSTOJ切换到Hydro啦！

直接放链接吧

https://tzhsoj.com/

很早以前立过的Flag，要把高中学校的内网 OJ弄到公网上

这个暑假乘着回学校就顺手做了一下

原版OJ的题目在

https://tzhsoj.com/d/TZHSOJ_OLD/p

题目被我删掉了一部分没有测试数据和出错的

入门用的SzNOI不再和原来的题目混杂在一起了

https://tzhsoj.com/d/SzNOI/p

主界面

新换的Hydro系统比以前用HUSTOJ那套系统强太多了不是吗qwq，遗憾的是刷题记录不保留了

以及新的服务器上云了，正常压力下的服务器是校内的老E5，遇到突发高压情况（比如比赛）的时候将会动态切换申请腾讯云服务器来避免评测队列卡死

升级过程就写了个脚本自动导题目这样qwq

牛客 1041D MobileService

✇Rei's Blog
2021年1月31日 00:43

题目链接:Mobile Service

这个题最简单的想法就是直接把三个人的位置直接都放进状态,然而这样子的话复杂度到了$O(N*L^3)$实在是难以接受的复杂度。

我们发现，员工的位置只要知道两个没有去服务上一个p[i]的人，第三个人一定在p[i]位置，因此我们知道其复杂度变为了$O(N*L^2)$已经是可以接受的状态了

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))
#define mmst3f(x) memset(x,0x3f,sizeof(x))
#define pb(x) push_back(x)

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f,MOD=1e9+7;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
//void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));} //警告,如非必须(如__int128),请不要使用快写

int l,n,ans=INF;
int p[1003]={3};//让p[0]作为起始点=3
int c[203][203];
int f[1003][203][203];

void work()
{
    scanf("%d%d",&l,&n);//l=read();n=read();
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++) scanf("%d",&c[i][j]);//c[i][j]=read();
    for(int i=1;i<=n;i++) scanf("%d",p+i);//p[i]=read();
    mmst3f(f); f[0][1][2]=0;
    for(int i=0;i<n;i++)//p[0]已知为3,因此从0开始往i+1转移,然后得到结果
    {
        for(int x=1;x<=l;x++)
        {
            for(int y=1;y<=l;y++)
            {
                int z=p[i],nxt=p[i+1],now=f[i][x][y];
                if(x==y || x==z || y==z) continue;
                f[i+1][x][y]=min(f[i+1][x][y],now+c[z][nxt]);//让z去
                f[i+1][z][y]=min(f[i+1][z][y],now+c[x][nxt]);//让x去
                f[i+1][x][z]=min(f[i+1][x][z],now+c[y][nxt]);//让y去
            }
        }
    }
    for(int x=1;x<=l;x++) 
        for(int y=1;y<=l;y++) 
        {
            //if(x==y || x==p[n] || y==p[n]) continue; //ans初始值==INF所以可以不用这句话
            if(f[n][x][y]<ans) ans=f[n][x][y];
        }
    cout<<ans<<endl;
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=1;//read();
    for(int Case=1;Case<=T;Case++)
    {
        //printf("Case #%d: ",Case);
        work();
    }
    return 0;
}

然后写完发现这样子的话就要去掉#define int long long

那么这个其实是可以滚动数组缩内存的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

for(int i=0;i<n;i++)//p[0]已知为3,因此从0开始往i+1转移,然后得到结果
{
    for(int x=1;x<=l;x++)
    {
        for(int y=1;y<=l;y++)
        {
            int z=p[i],nxt=p[i+1],now=f[i&1][x][y];
            if(x!=nxt && y!=nxt) f[(i+1)&1][x][y]=min(f[(i+1)&1][x][y],now+c[z][nxt]);//让z去
            if(z!=nxt && y!=nxt) f[(i+1)&1][z][y]=min(f[(i+1)&1][z][y],now+c[x][nxt]);//让x去
            if(x!=nxt && z!=nxt) f[(i+1)&1][x][z]=min(f[(i+1)&1][x][z],now+c[y][nxt]);//让y去
            f[i&1][x][y]=0x3f3f3f3f;
        }
    }
}

JLCPC 2018 (第12届吉林省大学生程序设计竞赛)

✇Rei's Blog
2021年1月13日 17:34
Featured image of post JLCPC 2018 (第12届吉林省大学生程序设计竞赛)

过程

开局一眼秒掉A，看了B发现就是个时区转换的语法题，ZJH自告奋勇写B题，然后我就开始和ZJQ去看C题了。大概四十分钟之后约莫是做出C了，就是个优先队列的水题==然后问ZJH有没有写好B，然后发现他写了四十分钟的时区转换语法题WA了。。。。。然后叫停ZJH，我自己来写时区转换，语法题一遍过。然后C思路和ZJQ已经论证完成，按思路写下来，在调样例的时候把Bug找到了，AC C题。写的时候ZJQ把概率DP推出来了，AC D题。接下来F发现自己以前做过了，全xor一起就行。

剩下一个计算机和E和贪心I题，以及线段树H感觉可以写（当然最后没写H）

推I题，三个人就我玩过完整的游戏王卡片，然后解释题面，发现是个分两种情况讨论的贪心，最后取 $max(ans1,ans2)$。让ZJQ给我造了组特殊的测试数据。然后思路对了就过了。

A 

 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

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;

void work()
{
    n=read();
    int ans=(int)sqrt(n);
    if(ans%2==1) printf("odd\n");
    else printf("even\n");
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=read();
    for(int Case=1;Case<=T;Case++)
    {
        printf("Case %lld: ",Case);
        work();
    }
    return 0;
}

B 

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int t,s,f;
string m,s1,s2;

void work()
{
    scanf("%d:%d",&s,&f);
    cin>>m>>s1>>s2;
    if(m[0]=='A'&&s==12) s=0;
    else if(m[0]=='P'&&s!=12) s+=12;
    if(s1=="Moscow") s-=3;
    else if(s1=="Beijing") s-=8;
    else if(s1=="Washington") s+=5;
    if(s2=="Moscow") s+=3;
    else if(s2=="Beijing") s+=8;
    else if(s2=="Washington") s-=5;
    if(s<0)
    {
        printf("Yesterday ");
        s+=24;
    }
    else if(s>=24)
    {
        printf("Tomorrow ");
        s-=24;
    }
    else printf("Today ");
    if(s==0) printf("12:%02d AM\n",f);
    else if(s>=1&&s<12) printf("%d:%02d AM\n",s,f);
    else if(s==12) printf("12:%02d PM\n",f);
    else printf("%d:%02d PM\n",s-12,f);

    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=read();
    for(int Case=1; Case<=T; Case++)
    {
        printf("Case %d: ",Case);
        work();
    }
    return 0;
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;
int fa[100003];
bool vis[100003];
priority_queue<pair<int,int> > q;

void INIT()
{
    n=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    while(!q.empty()) q.pop();
    mmst0(vis);
}

int find_root(int x) 
{
    return fa[x]==x?x:fa[x]=find_root(fa[x]);
}
int unionset(int x,int y)
{
    int xx=find_root(x),yy=find_root(y);
    if(xx>yy) swap(xx,yy);
    fa[xx]=yy; 
    return yy;
}

void work()
{
    for(int i=1;i<=n;i++)
    {
        q.push({read(),i});
    }
    while(!q.empty() && q.top().first>1)
    {
        int fi=q.top().first,se=q.top().second;
        q.pop();
        if(fi!=q.top().first) continue;//不能合并了
        if(q.empty()) break;
        int u=q.top().second;
        q.pop();
        int ee=unionset(se,u);
        q.push({fi-1,ee});
    }
    if(q.size()<2)
    {
        printf("NO\n");
        return;
    }
    int ee=q.top().second;
    for(int i=1;i<=n;i++)
    {
        if(find_root(i)==ee) vis[i]=true;
         else vis[i]=false;
    }
    printf("YES\n");
    for(int i=1;i<=n;i++) cout<<vis[i];
    cout<<endl;
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=read();
    for(int Case=1;Case<=T;Case++)
    {
        printf("Case %lld: ",Case);
        INIT();
        work();
    }
    return 0;
}

D 

 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

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int read()
{
	char c;
	int num,f=1;
	while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;
	num=(int)(c-'0');
	while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');
	return num*f;
}

int pp;
double dp[250];
void work()
{
	pp=read();
	double p=pp/100.0;
	memset(dp,0,sizeof(dp));
	dp[200]=1.0/p;
	for(int i=199;i>=4;i--)
	{
		double q=i/200.0;
		dp[i]=1+p*(1-q)*dp[min(i+4,200)]+(1-p)*dp[min(i+3,200)];
	}
	return;
}

signed main()
{
	int T=read();
	for(int Case=1;Case<=T;Case++)
	{
		work();
		printf("Case %d: %.10lf\n",Case,dp[4]);
	}
	return 0;
}

E 

 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

#include<bits/stdc++.h>

using namespace std;

int T,Case;

double deta(double a,double b,double c)
{
    double ans=b*b-4*a*c;
    ans=sqrt(ans);
    return ans;
}

int main()
{
    cin>>T;
    double r,h,x0,y0,z0,vx,vy,vz;
    while(T--)
    {
        cin>>r>>h;
        cin>>x0>>y0>>z0;
        cin>>vx>>vy>>vz;
        double a=vx*vx+vy*vy-vz*vz*r*r/(h*h);
        double b=2*x0*vx+2*y0*vy+2*r*r*vz/h-2*z0*vz*r*r/(h*h);
        double c=x0*x0+y0*y0-r*r+2*r*r*z0/h-r*r*z0*z0/(h*h);
        double t2=(-b-deta(a,b,c))/(2*a);
        printf("Case %d: %.10lf\n",++Case,t2);
    }
    return 0;
}

F 

 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

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

void work()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++)
    {
        ans^=max((int)0,min(i-2,read()-2));
    }
    printf("%lld\n",ans);
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=read();
    for(int Case=1;Case<=T;Case++)
    {
        printf("Case %lld: ",Case);
        work();
    }
    return 0;
}

H 

  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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

char op[10];
int t, n, q, l, r, x;

struct node {
    int l, r;
    int sum1, sum2;
    int vis, lazy1, lazy2, lazy3;
}segtree[maxn<<2];

void push_up(int rt) {
    segtree[rt].sum1 = (segtree[lson].sum1 + segtree[rson].sum1) % mod;
    segtree[rt].sum2 = (segtree[lson].sum2 + segtree[rson].sum2) % mod;
}

void push_down(int rt) {
    if(!segtree[rt].vis) return;
    int x = segtree[rt].lazy1, y = segtree[rt].lazy2, z = segtree[rt].lazy3;
    segtree[rt].vis = segtree[rt].lazy1 = segtree[rt].lazy2 = 0, segtree[rt].lazy3 = 1;
    segtree[lson].vis = segtree[rson].vis = 1;
    segtree[lson].lazy1 = (1LL * segtree[lson].lazy3 * x % mod + segtree[lson].lazy1) % mod;
    segtree[rson].lazy1 = (1LL * segtree[rson].lazy3 * x % mod + segtree[rson].lazy1) % mod;
    segtree[lson].lazy2 = (1LL * z * segtree[lson].lazy2 % mod + y) % mod;
    segtree[rson].lazy2 = (1LL * z * segtree[rson].lazy2 % mod + y) % mod;
    segtree[lson].sum1 = ((1LL * segtree[lson].sum2 * z % mod * x % mod + 1LL * segtree[lson].sum1 * z % mod) % mod + 1LL * y * (segtree[lson].r - segtree[lson].l + 1) % mod) % mod;
    segtree[rson].sum1 = ((1LL * segtree[rson].sum2 * z % mod * x % mod + 1LL * segtree[rson].sum1 * z % mod) % mod + 1LL * y * (segtree[rson].r - segtree[rson].l + 1) % mod) % mod;
    segtree[lson].sum2 = 1LL * segtree[lson].sum2 * z % mod * z % mod;
    segtree[rson].sum2 = 1LL * segtree[rson].sum2 * z % mod * z % mod;
    segtree[lson].lazy3 = 1LL * segtree[lson].lazy3 * z % mod;
    segtree[rson].lazy3 = 1LL * segtree[rson].lazy3 * z % mod;
}

void build(int rt, int l, int r) {
    segtree[rt].l = l, segtree[rt].r = r;
    segtree[rt].lazy1 = segtree[rt].lazy2 = 0;
    segtree[rt].lazy3 = 1;
    segtree[rt].sum1 = segtree[rt].vis = 0, segtree[rt].sum2 = 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    push_up(rt);
}

void update(int rt, int l, int r, int x) {
    if(segtree[rt].l == l && segtree[rt].r == r) {
        segtree[rt].vis = 1;
        segtree[rt].lazy2 = (10LL * segtree[rt].lazy2 + x) % mod;
        segtree[rt].lazy1 = (1LL * segtree[rt].lazy3 * x % mod + segtree[rt].lazy1) % mod;
        segtree[rt].sum1 = (10LL * ((1LL*segtree[rt].sum2 * x % mod + segtree[rt].sum1 % mod) % mod) % mod + x * (r - l + 1)) % mod;
        segtree[rt].sum2 = 100LL * segtree[rt].sum2 % mod;
        segtree[rt].lazy3 = 10LL * segtree[rt].lazy3 % mod;
        return;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) update(lson, l, r, x);
    else if(l > mid) update(rson, l, r, x);
    else {
        update(lson, l, mid, x);
        update(rson, mid + 1, r, x);
    }
    push_up(rt);
}

int query(int rt, int l, int r) {
    if(segtree[rt].l == l && segtree[rt].r == r) return segtree[rt].sum1;
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return (query(lson, l, mid) + query(rson, mid + 1, r)) % mod;
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif // ONLINE_JUDGE
    scanf("%d", &t);
    int icase = 0;
    while(t--) {
        scanf("%d%d", &n, &q);
        build(1, 1, n);
        printf("Case %d:\n", ++icase);
        while(q--) {
            scanf("%s%d%d", op, &l, &r);
            if(op[0] == 'w') {
                scanf("%d", &x);
                update(1, l, r, x);
            } else printf("%d\n", query(1, l, r));
        }
    }
    return 0;
}

I 

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;
const int maxn=1e5+3;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

struct Node
{
    int value,pos;
    bool operator <(const Node &d)const
    {
        return value<d.value;
    }
} node[maxn];

int T,Case,n,m,sum,sum1,ans,ans1,cnt;//cnt->防御个数
int a[maxn],b[maxn];

void work()
{
    n=read();m=read();
    ans=ans1=sum=sum1=cnt=0;
    for(int i=0; i<n; i++)
    {
        a[i]=read();
        sum+=a[i];
    }
    for(int i=0; i<m; i++) node[i].value=read();
    for(int i=0; i<m; i++)
    {
        node[i].pos=read();
        if(!node[i].pos) sum1+=node[i].value;
        if(node[i].pos) b[cnt++]=node[i].value;
    }
    sort(node,node+m);
    sort(a,a+n);
    bool flag=false;
    if(n>=m)
    {
        int i=n-1,j=m-1;
        for(; i>=0&&j>=0; i--)
        {
            if(node[j].value<=a[i]) j--;
            else break;
            if(!j) break;
        }
        if(!j) flag=true;
    }
    if(flag)
    {
        int j=0;
        for(int i=0; i<n&&j<cnt; i++)
            if(a[i]>=b[j])
            {
                j++;
                sum-=a[i];
            }
        if(j!=cnt) flag=0;
        else ans=sum-sum1;
    }
    int i=n-1,j=0;
    for(; i&&j<m; i--)
    {
        if(a[i]>=node[j].value)
        {
            if(!node[j].pos) ans1+=(a[i]-node[j].value);
            j++;
        }
        else break;
    }
    printf("Case %lld: %lld\n",++Case,max(ans,ans1));
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=read();
    for(int Case=1;Case<=T;Case++)
    {
        //printf("Case #%d: ",Case);
        work();
    }
    return 0;
}

POJ2279 Mr. Young's Picture Permutations

✇Rei's Blog
2021年1月13日 02:21

蛮有意思的一个DP,数据很小,但是直接开的话是会直接爆掉

做这个题是因为最近比较无头苍蝇，就刷李煜东的书和Steps

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n;
int s[6];

void work()
{
    while(n=read())
    {
        mmst0(s);
        for(int i=1;i<=n;i++) s[i]=read();
        int f[s[1]+1][s[2]+1][s[3]+1][s[4]+1][s[5]+1];
        mmst0(f);
        f[0][0][0][0][0]=1;
        for(int i=0;i<=s[1];i++)
        {
            for(int j=0;j<=s[2];j++)
            {
                for(int k=0;k<=s[3];k++)
                {
                    for(int l=0;l<=s[4];l++)
                    {
                        for(int m=0;m<=s[5];m++)
                        {
                            if(i<s[1]) f[i+1][j][k][l][m]+=f[i][j][k][l][m];
                            if(j<s[2] && j<i) f[i][j+1][k][l][m]+=f[i][j][k][l][m];
                            if(k<s[3] && k<j) f[i][j][k+1][l][m]+=f[i][j][k][l][m];
                            if(l<s[4] && l<k) f[i][j][k][l+1][m]+=f[i][j][k][l][m];
                            if(m<s[5] && m<l) f[i][j][k][l][m+1]+=f[i][j][k][l][m];
                        }
                    }
                }
            }
        }
        cout<<f[s[1]][s[2]][s[3]][s[4]][s[5]]<<endl;
    }
    return;
}

signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=1;//read();
    for(int Case=1;Case<=T;Case++)
    {
        //printf("Case #%d: ",Case);
        work();
    }
    return 0;
}

然后发现貌似MS更简单易懂一些(废话，哪有MS比DP难理解的)

 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

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int k;
int len[6];
ll dp[31][16][11][8][7];

ll dfs(int a,int b,int c,int d,int e)
{
    if(a<0||b<0||c<0||d<0||e<0)return 0;
    ll &opt=dp[a][b][c][d][e];
    if(opt)return opt;
    opt=dfs(a,b,c,d,e-1);
    if(d>e)opt+=dfs(a,b,c,d-1,e);
    if(c>d)opt+=dfs(a,b,c-1,d,e);
    if(b>c)opt+=dfs(a,b-1,c,d,e);
    if(a>b)opt+=dfs(a-1,b,c,d,e);
    return opt;
}

int main()
{
    while(scanf("%d",&k) && k)
    {
        memset(len,0,sizeof(len));
        memset(dp,0,sizeof(dp));
        dp[0][0][0][0][0]=1;
        for(int i=1; i<=k; i++) scanf("%d",len+i);
        printf("%lld\n",dfs(len[1],len[2],len[3],len[4],len[5]));
    }
    return 0;
}

最后看lyd书的题解发现这玩意的数学名称叫做杨氏矩阵…….有公式算的,wdnmd

 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

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll n,cnt,x,y,tmp,num[40],sum[5200];

int main()
{
    while(scanf("%lld",&n)&&n)
    {
        memset(sum,0,sizeof(sum));
        cnt=0,x=1,y=1;
        for(int i=1; i<=n; i++)scanf("%lld",&num[i]);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=num[i]; j++)
            {
                cnt++;
                for(int k=i+1; k<=n; k++)
                {
                    if(num[k]>=j)sum[cnt]++;
                    else break;
                }
                sum[cnt]+=num[i]-j+1;
            }
        for(int i=1; i<=cnt; i++)
        {
            x*=i;
            y*=sum[i];
            tmp=__gcd(x,y);
            x/=tmp;
            y/=tmp;
        }
        printf("%lld\n",x/y);
    }
    return 0;
}

HDUOJ 1271

✇Rei's Blog
2021年1月8日 18:22

其实是一道大水题,但是自己写的时候一开始居然没想到去枚举k就可以了,确实不擅长做数学题

证明

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define int long long
//#define int __int128
#define ull unsigned long long
#define mmst0(x) memset(x,0,sizeof(x))

using namespace std;
//using namespace __gnu_pbds;

const int INF=0x3f3f3f3f;

int read(){char c;int num,f=1;while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;num=(int)(c-'0');while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');return num*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}

int n,a,b,c;
int t[10000];

void work()
{
    while(n=read())
    {
        int cnt=0;
        for(int k=1;k<=n;k*=10)//枚举k,此处k为10^k
        {
            c=(n/k)/11;//去掉了后面k未之后就剩下前几位,即为c;
            b=n/k-c*11;//前k位减去11c就是b
            if((b!=0 || c!=0) && b<10)//b<10是存在进位
            {
                a=(n-b*k-11*c*k)/2;
                if(2*a+b*k+11*c*k==n) 
                    t[++cnt]=a+b*k+c*k*10;
            }
            b--;
            if((b!=0 || c!=0) && b>=0)
            {
                a=(n-b*k-11*c*k)/2;
                if(2*a+b*k+11*c*k==n) 
                    t[++cnt]=a+b*k+c*k*10;
            }
        }

        if(!cnt)
        {
            printf("No solution.\n");
        }
        else
        {
            sort(t+1,t+1+cnt,[](int a,int b){
                return a<b;
            });
            printf("%d",t[1]);
            for(int i=2;i<=cnt;i++) if(t[i]!=t[i-1]) printf(" %d",t[i]);
            printf("\n");
        }
    }
    return;
}

/*
N=2a+b*10^k+11c*10^k
*/
signed main()
{
    //ios::sync_with_stdio(false);cin.tie(NULL);
    int T=1;//read();
    for(int Case=1;Case<=T;Case++)
    {
        //printf("Case #%d: ",Case);
        work();
    }
    return 0;
}
❌
❌