zhangas

Pay more attention

0%

Veröffentlicht am

Let’s first consider below simple question.

What is the minimun complexity to find n’th Fibonacci Number?

We can find n’th Fibonacci Number in O(log n) time using $Matrix\quad Exponentiation$. In this post, a general implementation of Matrix Exponentiation is discussed.

For solving the problem, we are assuming a linear recurrence eqution like below:
F(n) = a * F(n - 1) + b * F(n - 2) + c * F(n - 3) for n >= 3  ....Equation (1)
where a, b, c are constants.

For this recurrence relation, it depends on three previous value.
Now we will try to represent Equation(1) in terms of the matrix.
|F(n)|                    |F(n - 1)|
|F(n - 1)| = Matrix 'C' * |F(n - 2)|
|F(n - 2)|                |F(n - 3)|
Now we need to fill the Matrix 'C'.
so according to our equation.
             |a b c|
Matrix 'C' = |1 0 0|
             |0 1 0|
so for n, the equation(1) changes to 
|F(n)|                     |F(2)|
|F(n - 1)| = C ^ (n - 2) * |F(1)|
|F(n - 2)|                 |F(0)|
So we can simply multiply our matrix 'C' n - 2 times and the multiply it with the matrix below to get the result.
|F(2)|
|F(1)|
|F(0)|
Multiplication can be done in O(Log n) time using Divie and Conquer algorithm for fast power.
There is rough code below.


typedef struct Mat{
    int m[105][105];
}Mat;
Mat a;
Mat multiply(Mat x, Mat y){
    // Creating an new matrix to store elements 
    // of the multiplication matrix
    Mat c;
    for(int i = 1; i <= 3; ++ i){
        for(int j = 1; j <= 3; ++ j){
            c.m[i][j] = 0;
            for(int k = 1; k <= 3; ++ k)
                c.m[i][j] += x.m[i][k] * y.m[k][j];
        }
    }
    return c;
    // return the result
}
Mat Matrix_fastpow(Mat a, Mat k){
    //initial values for matrix 'C'
    Mat res;
    res.m[1][1] = a;res.m[1][2] = b;res.m[1][3] = c;
    res.m[2][1] = 1;res.m[2][2] = 0;res.m[2][3] = 0;
    res.m[3][1] = 0;res.m[3][2] = 1;res.m[3][3] = 0;

    while(k){
        if(k & 1){
            res = multiple(a, res);
        }
        k >>= 1;
        a = multiple(a, a);
    }
    return res;
}

Veröffentlicht am

新建运动会

支持创建/ 删除运动会项目 且删除时需要输入管理员密码

设置运动会的地点、时间

输入比赛地点，运动会期间每一天上午、下午的开赛时间、结束时间

参赛人员分组

可以选择添加 本科组、研究生组、教职工组 每一个大组可以分为甲、乙两个小组 且每个组都分为男子组、女子组、混合组
大一默认为乙组，大二、三、四默认为甲组

支持导入修改代表队的简称及全称

①批量导入是按照每一行的顺序去填入表格，且代表队伍的简称和全程都可以有。
②直接人工填入表格。

为每一个竞赛组（格式为”本科A组男子”）去选择比赛项目

50m、100m…5000m的跨栏，短、长跑，障碍，仰卧起坐等等。
且支持新建插入自己设定的项目

运动员报名限制

①每一个学院的代表队可以在当前组最多报名人数
例如：体育学院代表队在本科A组里的所有项目中可以报名多少人
②每一个人限制最多报名多少项比赛
例如：体育学院的甲同学 最多报名两项比赛
我认为报名这里可以让学院的代表队里人数多一些，可以出现替补上场

竞赛组的比赛器材规格

例如：铅球的重量

名次录取排序和晋级方式

①预赛中多少队晋级多少队
②决赛中取前多少个队伍获得对应的奖牌

预赛、决赛的每组中的分道方式

①随机分道
②按照先前成绩分道

填入各项的项目记录

一级：校记录
二级：县记录
三级：市记录

（可选）按照比赛成绩去判定运动员的等级

少年级、三级、二级、一级、健将、国际健将。

设置计分的办法

七分制：前6名 7 5 4 3 2 1
九分制：前八名 9 7 6 5 4 3 2 1
名次分制度：可以自己为名次赋值
去给学院代表队统计集体分数
为照顾选手，可以选择在参赛并完成比赛的基础上添加基础分

Veröffentlicht am Bearbeitet am

在PTA 上 L2-026 小字辈这样一道题中 因为STL 的不当使用，出现了段错误的问题，在仔细与李同学讨论后，发现了如下原因。题目链接

问题一 创建新队列实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
queue<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;
        queue<int> Q2;
        Q = Q2; // 创建一个新的队列来实现清空操作

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这种清空操作出现了问题，在于当前层的go( ) 函数只有return 后才会释放掉内存，但是一直往深度访问的时候，每一层开辟的新的queue的空间并没有被释放掉，因此造成了内存的堆积，产生爆栈。

问题二 借助deque自带的clear()函数来实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
deque<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q.clear(); // 会清空元素并不会释放掉内存

        Q.push_back(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push_back(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

自带的clear() 函数会清空元素并不会释放掉内存
而pop_back() 函数会将元素和内存一起释放掉

可以借助以下两个函数来验证

1
2
3
deque<int> Q;
Q.size(); // 元素的个数 相当于length 属性
Q.capacity(); // 最大容量（开辟的空间） 相当于queue_size 属性

以下有两种解决的方法

1. 手写清空函数

1
2
3
4
5
6
7
    void Queue_Clear()
{
    while(!Q.empty()){
        Q.pop();
    }
}

2. 在全局变量中多声明一个Queue 来进行辅助清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
queue<int> Q;
queue<int> Q2;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q = Q2; // 通过赋值来清空队列

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这样不会产生内存堆积的现象，解决问题。

Veröffentlicht am Bearbeitet am

C.数组平均
游游拿到了一个大小为n的数组，数组第i个数为a_i。
游游可以选择一些元素，使得这些元素都等于它们的平均数。
eg.假设数组为 [5, 4, 2, 4]，游游选择第一个和第三个元素，最终数组将变成 [3.5, 4, 3.5,4]
游游最多可以选择k个元素，她希望最终数组最大值和最小值的差尽可能小。你能帮她求出这个差吗？

贪心+前缀和
可以发现选中的元素个数越多，数组的max - min 的差值越小，同时维护前缀和

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
double a[200005];
double b[200005];
void solve(){
    int n = read(), k = read();
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
    }
    // 这里需要排序，因为想要让极差小 就要对最小值和最大值操作
    sort(a + 1, a + 1 + n);

    for(int i = 1; i <= n; ++ i){
        b[i] = b[i - 1] + a[i];
    }
    double ans = 1e9;
    // i 枚举左侧选中的个数
    for(int i = 0; i <= k; ++ i){
        // j 枚举右侧选中的个数 
        int j = k - i;
        // 求左右两侧选中元素的平均值
        double ave = (b[i] + b[n] - b[n - j]) / k;

        //未选中的区间[i + 1, n - j] 此刻内部是有序的

        //计算这一情况的下的最小值和最大值
        double mi = min(a[i + 1], ave);
        double ma = max(a[n - j], ave);

        ans = min(ans, ma - mi);
    }
    printf("%.7lf", ans);
}

D.游游出游
游游准备去开车旅行，她初始在1号城市，准备前往n号城市。
游游打开了携程，她查询到了地图上有若干城市，城市之间有一些道路连接。每条道路有承重限制，当游游的车重量超过了承重时，她就不能走这条道路。游游是一个贪心的人，她希望总路程不超过h的前提下，携带尽可能多的物品出行。游游想知道，自己的车最多重量能达到多少？

二分 + dijkstra 二分最大的答案的同时 通过跑最短路

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
    typedef struct node{
	    int v, w, d;
        }node;
    void solve(){
	int n = read(), m = read(), h = read();
	vector<vector<node>> g(n + 1);
    vector<int> dist(n + 1);
    vector<int> st(n + 1);
    // 建边
	for(int i = 0; i < m; ++ i){
		int u = read(), v = read(), w = read(), d = read();
		g[u].push_back({v, w, d});
		g[v].push_back({u, w, d});
	}
	function<int(int)> check = [&](int mid) -> bool{
		priority_queue<PII, vector<PII>, greater<PII> > q;
		q.push({0, 1});
		for(int i = 1; i <= n; ++ i) st[i] = 0, dist[i] = 0x3f3f3f3f;
		dist[1] = 0;
		while(q.size()){
			PII t = q.top();
			q.pop();
			
			int distance = t.first, ver = t.second;
			if(st[ver]) continue;
			st[ver] = 1;
			
			for(node &it : g[ver]){
				// 如果质量超过路径的最大承重量
				if(mid > it.w){
					continue;
				}
                // 更新距离
				if(dist[it.v] > dist[ver] + it.d){
					dist[it.v] = dist[ver] + it.d;
					q.push({dist[it.v], it.v});
				}
			}
		}
        //必须满足路径和不超过 h
		return dist[n] <= h;
	};

    int l = 0, r = 1e9;
	while(l < r){
		int mid = l + r + 1 >> 1;
		if(check(mid)){
			l = mid;
		}
		else{
			r = mid - 1;
		}
	}
	if(!check(l)) cout << "-1";
	else cout << l;
}

Veröffentlicht am

begin()和end()产生指向容器内第一个元素和最后一个元素的下一个位置的迭代器

st.begin() 返回一个迭代器，它指向容器第一个元素

st.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置

st.rbegin() 返回一个逆序迭代器，它指向容器最后一个元素

st.rend() 返回一个逆序迭代器，它指向容器第一个元素前面的位置

返回set 容器中最后一个元素: st.rbegin()

Veröffentlicht am

解决主板电源与机箱风扇冲突造成的电源接触不良问题

将风扇与主板都拆下，先接主板电源，再将风扇贴紧装上。

Power_Fan_clash

摄像头需要两个接口USB 3.0 和SMA 公头

USB 3.0接口 由主板20Pin 接口转USB 3.0提供
SMA公头 由 E90-DTU 右侧的N 型母头 提供

E90-DTU

RS485接口的分线问题：

将黑线接入GND 接口，将黄线接入VCC 接口

GND_VCC
基于样板图如下：
model_E90-DTU

下次任务重点

• 1.完成接线和分线任务
• 2.连接摄影机调试图像输入
• 3.学习田径运动会管理软件的使用流程

Veröffentlicht am Bearbeitet am

单链表

原地反转单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* reverseList(ListNode* L){
    //如果没有头节点 需要建立头节点
    ListNode * head = (ListNode *)malloc(sizeof (ListNode));
    head -> next = L;

    //如果已有头节点
    auto p = head -> next;
    head -> next = NULL;
    while(p){
        auto t = p -> next; // 暂存p下一节点
        p -> next = head -> next;
        head -> next = p;
        p = t;
    }
    return head -> next;
}

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
LinkList L = (LNode *)malloc(sizeof (LNode));
int n;cin>>n;
for(int i = 0; i < n; ++ i){
    int t;cin>>t;
    auto p = (LNode *)malloc(sizeof (LNode));
    p -> val = t;
    p -> next = L ->next;
    L -> next = p;
}

递归建立单链表

1
2
3
4
5
6
7
8
9
10
11
void creat(LinkList L,int n){
    if(!n)return;
    else{
        creat(L, n - 1);
        int t;scanf("%d", &t);
        LNode *p = (LNode *)malloc(sizeof (LNode));
        p -> val = t;
        p -> next = L -> next;
        L -> next = p;
    }
}

双指针求倒数第k项

1
2
3
4
5
6
7
8
9
10
11
12
int get_k_LinkList(LinkList L, int k){
    LNode *fast = L, *slow = L;
    for(int i = 0; i < k; ++ i){
        fast = fast -> next;
    }
    while(fast){
        fast = fast -> next;
        slow = slow -> next;
    }
    return slow -> data;
}

Veröffentlicht am

E - Equalising Audio

题目链接
签到,保持$a_1$到$a_n$比例不变，给出K输出满足$K==\frac{1}{n}\sum a_i^2$的$a_i$

1
2
3
4
5
6
7
8
9
10
11
12
   int n=read(),k=read();
   int cnt=0;
for(int i=1;i<=n;i++){
	a[i]=read();
	cnt+=a[i]*a[i];//求出总份数
}
double per;
if(!cnt)per=0;//可能全为0 这里特殊处理下
else per=sqrt(x*n*1.0/cnt);//一份的大小
for(int i=1;i<=n;i++){
	printf("%.9lf ",per*a[i]);//乘以对应的份数
}

I - Imperfect Imperial Units

题目链接
n次definition

1
1 <unit> = <value> <unit>

q次query

1
<value> <unit> to <unit>

保证每次询问前都曾有定义过

1
2
3
4
5
6
7
int cnt;
int id(string s){
    if(!mp[s]){
        mp[s]=++cnt;
    }
    return mp[s];
}

并查集维护是否可以兑换,输出”impossible”的情况

1
2
3
4
5
6
7
8
9
10
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
bool check(string a,string b){
    int ia=id(a),ib=id(b);
    ia=find(ia),ib=find(ib);
    if(ia==ib)return true;
    return false;//"impossible"的情况
}
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
string t;
int ans;
void dfs(int t,int b,double e){
    if(t==b){
        ans=e;
        return ;
    }
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];
        double d=w[i];
        if(!st[j]){
            st[j]=1;
            dfs(j,b,e*d);
            st[j]=0;
        }
    }
}
void add(int a,int b,double c){
    e[idx]=b;
    ne[idx]=a;
    w[idx]=c;
    h[a]=idx++;
}
void de(){
    double a;cin>>a;
    string s1;cin>>s1;
    cin>>t;
    double b;cin>>b;
    string s2;cin>>s2;
    int ida=id(s1),idb=id(s2);
    add(ida,idb,b);
    add(idb,ida,1.0/b);
    ida=find(ida),idb=find(idb);
    f[ida]=idb;
}
void qu(){
    double a;cin>>a;
    string s1;cin>>s1;
    cin>>t;
    string s2;cin>>s2;
    if(!check(s1,s2))puts("impossible");
    else{
        memset(st,0,sizeof(st));
        int ida=id(s1),idb=id(s2);
        st[ida]=1;
        dfs(ida,idb,1.0);
        printf("%.7g",ans);
    }
}

L - Lowest Latency

求三维平面内 距离最小的两点
使用分治的思想 按照x轴大小排序后 分为左，中，右三部分
最短距离有三种可能
1.左部分之间的两点
2.右部分之间的两点
3.跨越中间的两点
求出1，2两部分的最小值$d=min(d1,d2)$后，借助贪心的思想，将与中间点距离小于d的点放入容器内，借助$O(M^2)\quad M<<N$遍历

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
const int N = 1e5+5;
struct node{
	int x,y,z;
}a[N];
bool cmp(node a,node b){//按照x轴的大小排序
	if(a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
double dist(node a,node b){//求任意两点之间的距离
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
int t[N];//存储与中间点距离小于d的点的下标
double merge(int l,int r){
    if(l==r)return 0x3f3f3f3f;
    if(l+1==r)return dist(a[l],a[r]);//只剩下两点
    
    int mid=l+r>>1;
    double d1=merge(l,mid);
    double d2=merge(mid+1,r);
    
    double ans=min(d1,d2);

    int idx=0;
    for(int i=l;i<=r;i++){
        if(fabs(a[i].x-a[mid].x)<ans){
            t[++idx]=i;
        }
    }
    //遍历
    for(int i=1;i<=idx;i++){
        for(int j=i+1;j<=idx;j++){
            int td=dist(a[t[i]],a[t[j]]);
            ans=min(ans,td);
        }
    }
    return ans;
}

Veröffentlicht am Bearbeitet am

SDKD2023 Summer TeamContest A——NCC_17011

C - Cosmic Commute

题目链接
无向图从1到n存在m条light trains
m>=n-1 所以点1和n一定是联通的
存在k个wormhole 可以随机传送到另外k-1个位置 且at most once
求最少经过多少条light trains 可以到达点n
思路

• Compute dist(s, w) and dist(w, t) for each wormhole w and sum S using two BFS from s and t.
• Determine the wormhole you should enter to minimize the expected distance.
• If you enter wormhole w , the expected distance from s to t is
$$dist_w=dist(s,w)+\frac{1}{k-1}\sum dist(w_1,t)(w_1≠w)=dist(s,w)+\frac{1}{k-1}(S-dist(w_1,t))\with\quad S=\sum dist(w_1,t)$$

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
//bfs两次 求任一点到1和n的距离dist1数组和dist2数组
void bfs(int u,int dist[]){
	memset(st,0,sizeof(st));
	queue<int>q;
	q.push(u);
	dist[u]=0;
	st[u]=1;
	while(q.size()){
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];//t->j
			if(dist[j]>dist[t]+1){
				dist[j]=dist[t]+1;
				if(!st[j]){
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
}
signed main(){
	memset(dist1,0x3f,sizeof(dist1));
	bfs(1,dist1);
	memset(dist2,0x3f,sizeof(dist2));
	bfs(n,dist2);
	int sum=0;//计算S 所有wormhole点到n的距离之和
	for(int i=1;i<=k;i++){
		sum+=dist2[hole[i]];
		dist1[hole[i]]*=(k-1);
	}
	int mi=dist1[n]*(k-1);//不使用wormhole的最短距离
	for(int i=1;i<=k;i++){
		int t=sum-dist2[hole[i]]+dist1[hole[i]];
		mi=min(mi,t);
	}
	int t=gcd(mi,k-1);
	cout<<mi/t<<'/'<<(k-1)/t;
}

D - DnD Dice

题目链接
读了一遍题 dp？ 数学正态分布！
两个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 5 4 3 2 1
一个4面骰子和一个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10
1 2 3 4 5 4 3 2 1
观察可发现数字出现的次数成正态分布
需要注意分奇偶使用两个指针l r向前后移动输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[25];
signed main(){
	a[4]=read(),a[6]=read(),a[8]=read(),a[12]=read(),a[20]=read();
	int mi=a[4]+a[6]+a[8]+a[12]+a[20];
	int ma=a[4]*4+a[6]*6+a[8]*8+a[12]*12+a[20]*20;
	int mid=mi+ma>>1;
	if((ma+mi)%2==0){
		cout<<mid<<' ';
		for(int l=mid-1,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	else{
		for(int l=mid,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	return 0;
}

E - Eszett

题目链接
签到 ss转化为G输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
signed main(){
	string s;cin>>s;
	for(auto &i:s)i=tolower(i);
	cout<<s<<endl;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]=='s'&&s[i+1]=='s'){
			string ans=s.substr(0,i);
			ans+='B';
			ans+=s.substr(i+2,s.size()-1);
			cout<<ans<<endl;
		}
	}
	return 0;
}

I - Investigating Frog Behaviour on Lily Pad Patterns

题目链接
set存储目前所以的空位 且最多最多移动到ma+q的位置上(最右端的青蛙连续跳q次)
借助upper_bound函数查找第一个大于x的数

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
int a[200005];
int mp[1000005];
set<int>st;
int ma;
signed main(){
	int n=read();
    for(int i=1;i<=n;i++){
		a[i]=read();
        mp[a[i]]=1;
        ma=max(ma,a[i]);
    }
    int q=read();
    for(int i=1;i<=ma+q;i++) {
        if(!mp[i])st.insert(i);
    }
    for(int i=0;i<q;i++){
        int tt=read();
        auto t=st.upper_bound(a[tt]);
        int b=*t;
        cout<<b<<endl;
        st.erase(t);//删掉空座t
        st.insert(a[tt]);//添加产生的新空座 注意该青蛙后面的frog可以到达这个位置
        a[tt]=b;//更新跳跃青蛙的位置
    }
}

G - German Conference for Public Counting

题目链接
每个数字都可以由0-9的卡牌组成
求从0-N需要多少张不同的卡牌
特判前两位大小情况 0一定是长度-1张

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
int cnt[15];
bool check(char c,string s){
	for(auto &i:s){
		if(i<c)return false;
	}
	return true;
}
signed main(){
	int n=read();
	string a=to_string(n);
	if(n<10)cout<<n+1;
	else{
		int len=a.size();
		for(int i=1;i<a[0]-'0';i++){
			cnt[i]=len;
		}
		cnt[0]=len-1;
		if(a[0]<a[1]){
			cnt[a[0]-'0']=len;
		}
		else if(a[0]==a[1]){
			if(check(a[0],a))cnt[a[0]-'0']=len;
			else a[a[0]-'0']=len-1;
		}
		for(int i=0;i<=9;i++){
			if(!cnt[i])cnt[i]=len-1;
		}
		int ans=0;
		for(int i=0;i<=9;i++)ans+=cnt[i];
		cout<<ans;
	}
	return 0;
}

L - Loop Invariant

题目链接
首先给出balanced的定义->可以通过不断插入括号的操作获得的序列
特点是序列内的括号是一一对应存在的
将括号序列的前后连起来 求是否存在切割点满足切割后仍是balanced序列但不于前序列相同
思路: 先将序列分解成对应的子序列 再将序列复制前后联通 剪枝N^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
string t[1000010];
signed main(){
	string s;cin>>s;
	int len=s.size();
	int l=0,r=0;
	int p=0;
	int cnt=0;
	for(int i=0;i<len;i++){
		if(s[i]=='(')l++;
		else r++;
		if(l==r&&l&&r){
			t[++cnt]=s.substr(p,i-p+1);
			p=i+1;
			l=0,r=0;
		}
	}
	int f=0;
	for(int i=cnt+1;i<=cnt*2-1;i++){
		t[i]=t[i-cnt];//复制一遍 在遍历的时候满足前后联通
	}
	for(int i=2;i<=cnt;i++){
		if(t[i]==t[i-1]&&t[i+cnt-1]==t[i+cnt-2])continue;
        //剪枝 如果移动后与移动前的前后端都不变 那么一定不满足
		string tt="";
		for(int j=i;j<i+cnt;j++){
			tt+=t[j];
		}
		if(tt!=s){
			cout<<tt;
			return 0;
		}
	}
	cout<<"no";
	return 0;
}

M - Mischievous Math

题目链接
给出数d(1<=d<=100)构造出a b c三个数(1<=a,b,c<=100)两两不同
且满足a，b，c通过加减乘除运算 且a,b,c至多用一次后一定不等于d

1
2
3
4
5
6
7
8
signed main(){
	int n=read();
	if(n>=10)cout<<"1 2 3";//显然1 2 3 怎么运算也不会超过9
	else if(n>2)cout<<"98 99 100";
	else if(n==2)cout<<"96 99 100";
	else if(n==1)cout<<"96 98 100";
	return 0;
}

Summary

1.首次参加SDKD夏季集训 体验到前3h小时读题 后2h写题的训练方式 遗憾的是没有到现场参加
2.有不少题赛后发现仔细理解题目后 还是可以完成的,看到没有人去开新题 就不敢自己去试试。
3.代码模板熟练情况，构造题的思维，还有边界条件的处理，复杂度的剪枝优化等，需要强化。