以后学习这种解题写法
一道简单模拟
当时卡了一会儿就是因为“当前双方比分已经使得无论之后的罚球结果如何都不会影响比赛的结果”没有转过来 用了一个变量记轮数
其实不用 只需要两个新变量记剩下几个球可以进就可以了

[A模拟点球] [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
#include<bits/stdc++.h>
using namespace std;
void work()
{
	string s;
	cin>>s;
	int a=0,b=0,la=5,lb=5;
	for(int i=0;i<10;i++){
		if(i%2){
			lb--;
			if(s[i]=='1'){
				b++;
				if(b>a+la){
					printf("%d\n",i+1);
				
					return;
				}
			}else{
				if(a>b+lb){
					printf("%d\n",i+1);
					return;
				}
			}
		}else{
			la--;
			if(s[i]=='1'){
				a++;
				if(a>b+lb){
					printf("%d\n",i+1);
					return;
				}
			}else{
				if(b>a+la){
					printf("%d\n",i+1);
					return;
				}
			}
		}
		
	}
	printf("-1\n");
}

int main()
{
	int m;
	cin>>m;
	while(m--)
	{
		work();
	}
	return 0;
}

头一次遇到这种诈骗题 说是dfs 其实不用还原拼图
直接总造价=给出拼图的造价+确实拼图的造价

[拼图] [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
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int T; 
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		int ans=10;  
		string s;
		for(int i=0;i<n*n-1;i++)
		{
			cin>>s;
			for(int j=0;j<4;j++)
			{
				if(s[j]=='1') ans++;
				else if(s[j]=='2') ans--;
			}
		 } 
		 cout<<ans<<endl;
	 }
	return 0;
 }

实际上就是推数学公式
首先得读懂题意 大致就是给了(0,0) (x,y)的一个矩形 给你一个点xp yp作为顶点
求这个点与其对角顶点构成的矩形和之前矩形的 交集/并集最大
实际上就要分类讨论xp yp对于x y的相对位置
如果在右上 那么对角顶点肯定是0 0
如果在左下 枚举(0,0)(x,y)的四个顶点
在左上 枚举(0,0) (x,0)两个顶点
在右下 枚举(0,0) (y,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
#include<bits/stdc++.h>
using namespace std;

int x,y,px,py;
 
void work()
{
    cin>>x>>y>>px>>py;
    double ans;
    if(px<=x&&py<=y)ans=1.0*max({px*py,(x-px)*py,px*(y-py),(x-px)*(y-py)})/(x*y);
    else if(px>x&&py>y)ans=1.0*x*y/(px*py);
    else if(px<=x)ans=max(1.0*y*px/(x*y+px*(py-y)),1.0*y*(x-px)/(x*y+(x-px)*(py-y)));
    else ans=max(1.0*x*py/(x*y+py*(px-x)),1.0*x*(y-py)/(x*y+(y-py)*(px-x)));
    cout<<ans<<endl;
}
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(9);
    int _=1;
    cin>>_;
    while(_--)
        work();
    return 0;
}

前面是快读模板
当时看到是动态规划就放弃了 学都没学到
但是现在看来其实非常巧妙
首先满足条件:字符串长为n m个字符为1
所以怎么坏区间总数最少呢?
那么就是
前缀都是100 100 100 这样是好区间
把1都堆到最后 这样一个坏区间就占了3个1
枚举i 前i个都变成100 100这种 后面全部是1 当前得出坏区间个数和之前答案取小的

[本题主要考查dp] [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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const int INF = 0x3f3f3f3f;
inline ll read() {
    char ch;
    ll x = 0;
    bool f = true;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f ^= f;
    for (; isdigit(ch); ch = getchar())
        x = (x << 3) + (x << 1) + ch - 48;
    return f ? x : -x;
}
void solve(){
    int n=read(),m=read(),t = n - m;
    vector<int> s;
    while(m || t){
        if(m)s.push_back(1),m--; 
        if(t)s.push_back(0),t--;
        if(t)s.push_back(0),t--;//这三步就巧妙实现了100100..1111
    }
    int ans = 0 ;
    for(int i=1;i<n-1;i++)
        if(s[i] + s[i-1] + s[i+1] >=2)
            ans ++;
    cout << ans <<"\n";
}
int main() {
    int T = 1;
    for (int i = 1; i <= T; i++)
        solve();
    return 0;
}

此处跳过两道dp 日后填坑