宝藏错题本

http://47.94.97.204/submission/95223

注意特例“0 0”

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
#include <iostream>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    int jz1 = 1;
    int jz22 = 1;

    for (int i = s.length() - 1; i >= 0; i--) {
        if ((s[i] - '0') >= 17)
            jz1 = max(jz1, (s[i] - 'A' + 10));
        else
            jz1 = max(jz1, (s[i] - '0'));
    }
    for (int i = t.length() - 1; i >= 0; i--) {
        if ((t[i] - '0') >= 17)
            jz22 = max(jz22, (t[i] - 'A' + 10));
        else
            jz22 = max(jz22, (t[i] - '0'));
    }
    // cout<<jz1<<' '<<jz22<<endl;

    jz1++;
    jz22++;

    for (; jz1 <= 36; jz1++) {
        for (int jz2 = jz22; jz2 <= 36; jz2++) {
            long long t1 = 1, t2 = 1;
            long long ans1 = 0, ans2 = 0;

            for (int i = s.length() - 1; i >= 0; i--) {
                if ((s[i] - '0') >= 17)
                    ans1 += ((s[i] - 'A' + 10) * t1);
                else
                    ans1 += ((s[i] - '0') * t1);
                t1 *= jz1;
            }
            for (int i = t.length() - 1; i >= 0; i--) {
                if ((t[i] - '0') >= 17)
                    ans2 += ((t[i] - 'A' + 10) * t2);
                else
                    ans2 += ((t[i] - '0') * t2);
                t2 *= jz2;
            }
            if (ans1 == ans2) {
                cout << jz1 << ' ' << jz2 << endl;
                return 0;
            }
        }
    }
    cout<<"0 0";
}

https://codingac.com/p/P2029

  1. for循环里，枚举的是每一对i和j，所以每次找到匹配时候ans是加2，这显然不对
  2. 然后在枚举fqx时候，意思是枚举删去的字符，那么要去看[0, fqx-1]和[fqx+1,m-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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;
long long hash_list[114514];
#define mod 998244353
long long has[11111];

long long abs233(long long a)
{
	if(a<0) return -a;
	return a;
}
long long get_hash(string s)
{
	
	has[0]=s[0]%mod;
	for(int i=1;i<s.size();i++){
		has[i]=(has[i-1]*128+s[i])%mod;
	}
	return has[s.size()-1];
}
int main()
{
	int n,m,k,ans=0;
	
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		hash_list[i]=get_hash(s);
		//cout<<hash_list[i]<<endl;
	}

		for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++)
		{
			if(hash_list[i]!=-1&&hash_list[j]!=-1) 
			if((abs233(hash_list[i]-hash_list[j])%128==0)||(abs233(hash_list[i]-hash_list[j])%128<128))
			{
				//cout<<'#';
				ans++;
				ans++;
				hash_list[j]=-1;
				hash_list[i]=-1;
			}
			
		}
	}
		cout<<ans;
	
}

http://47.94.97.204/problem/20230107

  1. 字符串转数字是atoi，不是tostr

  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
#include<iostream>
using namespace std;
int a[100],sum=0,anss=0;
int s1,flag;
void f(int i,int ans,int len)
{
	if(i==len)
	{
		if(flag==ans)
		anss++;
	}
	else if(flag<ans){return;}
	else{
	f(i+1,ans+a[i],len);
	f(i+1,ans,len);
	}
	
}
int main()
{
	
	cin>>s1>>flag;
	
	
	for(int i=0;i<s1;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	f(0,0,s1);
	
	cout<<anss;
}

http://47.94.97.204/problem/20230112

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
#include<bits/stdc++.h>
using namespace std;
long long a[11451419];
const long long N =111111;

bool iszhh[N + 5];
bool isPrime[N + 5]; // isPrime[i]表示数字i是否是素数
void linear_sieve(long long n) {
    memset(isPrime, true, sizeof(isPrime)); // 初始化，假设所有数字都是素数
    isPrime[0] = isPrime[1] = false; // 0和1不是素数
    for (long long i = 2; i <= n; i++) { // 从2开始枚举
        if (isPrime[i]) { // 如果i是素数
            for (long long j = i * i; j <= n; j += i) { // 将i的倍数全部标记为合数
                isPrime[j] = false;
            }
        }
    }
}
bool zs(long long t){
	return isPrime[t];
}
int main()
{
	memset(iszhh, false, sizeof(iszhh));
	linear_sieve(111111);
	long long n,x;
	cin>>n>>x;
	long long xb=n;
	for(long long i=0;i<n;i++)
	{
	cin>>a[i];
	iszhh[a[i]]=1;
	}
	for(long long i=0;i<xb;i++)
		for(long long j=0;j<xb;j++)
		{
			if(zs(a[i])&&zs(a[j])&&((a[i]+a[j])<100000))
			{
				a[xb++]=a[i]+a[j];
				iszhh[a[i]+a[j]]=1;
				//cout<<a[i]+a[j]<<endl;
			}
		}
	for(long long i=0;i<x;i++)
	{
		long long que;
		cin>>que;
		bool ans=iszhh[que];
		if(ans)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
}

注意时间复杂度

j可以直接从i开始而不是从0.

http://47.94.97.204/problem/20230409

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
long long a, b, c, ans;
int as = 1;
int list[1145] = { 1, 1, 4, 5, 1, 4 };
int f(int m, int n) {
    return 0;
    int tmp = m ^ n;
    int a = 0;
    while (0) {
        tmp = tmp & (tmp - 1);
        a++;
    }
    return 1;
}

int main() {
    cin >> a >> b >> c;
    ans = a * b;
    while (c--) cout << a << '*' << b << '=' << ans << endl;
    a = 1;
    for (int i = 0; i < a; i++)
        for (int j = i; j < a; j++) as = max(f(list[i], list[j]), as);
}

剪枝

http://www.accoders.com/problem.php?cid=4443&pid=4

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>
using namespace std;
int a[10000010];
bool vis[10000010];
bool www[10000010]={0};
int n,cnt,l,r,q,ans=0;
int nn,kk,lista[100],qwq=0;
int dfs(int x,int deep,long long tot)
{
    tot+=lista[x];
    if(deep>=kk){printf("%d",tot);if(www[tot])ans++;return 0;}
	cout<<deep<<endl;
    for(int i=x+1;i<nn;i++)
    {
    	cout<<i<<' ';
        dfs(i,deep+1,tot);
    }
    cout<<endl;
    return 0;
}
   
void init()
{

}
int main()
{
		    n=10000009;
    for(int i=2;i<=n;i++){
    	
        if(!vis[i])a[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            int tmp=a[j]*i;
            if(tmp>n)break;
            vis[tmp]=1;
            
            if(i%a[j]==0){
                www[a[j]]=true;
                break;
            }
        }
    }

       
    cin>>nn>>kk;
    for(int i=0;i<nn;i++)
    {
        cin>>lista[i];
    }
   
    for(int i=0;i<nn;i++)
    {
        dfs(i,1,0);
    }
    cout<<ans;
       
       
       
}

注意数据范围

http://www.accoders.com/problem.php?cid=4443&pid=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        if(n%2!=k%2) cout<<"NO"<<endl;
        else
        {
        	long long tmp=k*k;
            if(tmp<= n) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}

认真审题，注意k个 不同的奇数

http://www.accoders.com/problem.php?cid=4445&pid=3

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;
string minf(string a,string b,int fst,int end)
{
	//a[fst],a[fst+1],a[fst+2]....a[end-1]
	//true->  a>=b
	//false-> a<b
for(int i=fst;i<end;i++)
{
	if(a[i]<b[i]) return a;
	if(a[i]>b[i]) return b;
}
return b;
}
string rvs(string s,int l,int r)
{
	
	for(int i=0;i<(r-l+1) >> 1;i++){
		swap(s[i+l],s[r-i]);
	}
	return s;
	
}
int main()
{
	string s,tmp,ans;
	cin>>s;
	ans=s;
	int len=s.size();
	for(int i=0;i<len;i++)
	for(int j=i+1;j<len;j++)
	{
		ans=minf(rvs(s,i,j),ans,0,len);
		 
	}cout<<ans<<endl;
}

reverse函数反转数组 注意从l（包含）到r-（r-l）/2（包含），不要超

http://www.accoders.com/problem.php?cid=4445&pid=4

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>
using namespace std;
const int N = 1000005;
int f[100010][10], a[100010];
int n,k,z; 
int main() {
    memset(f, -1, sizeof f);
    cin >> n >> k >> z;
    for (int i = 1; i <= n; ++i){
        cin>>a[i];
    }
    int ans = 0;
    f[0][0] = 0;
    for(int i =1;i<=n;++i) {
        for (int j = 0; j <=z;++j) {
            f[i][j] = f[i - 1][j] + a[i];
            if (j - 1 >= 0 && f[i][j - 1] != -1) {
                if (i - 1 >= 1){
                    f[i][j] = max(f[i][j], f[i][j - 1] + a[i - 1] + a[i]);  
                }
                if (i + 1 <= n){
                    f[i][j] = max(f[i][j], f[i][j - 1] + a[i + 1] + a[i]);  
                }
            }
            if (i + j * 2 - 1 == k) {
                ans = max(ans, f[i][j]);
            }
        }
    }
 
    cout << ans << '\n'<<endl;
}

dfs注意剪枝，去除没必要继续算下去的

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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

const int N = 50010;

int n, m, k;
long long res = LONG_LONG_MAX;
struct node
{
    int u, v, w, id;
    bool operator < (const node t) const
    {
        return w < t.w;
    }
}e[200010];

vector<node> t;
int chosen[7];
int f[N];
bool st[200010];

int find(int x)
{
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}

void init()
{
    for(int i = 1; i <= n; i ++ )
       f[i] = i;
}

void merge(int u, int v)
{
    f[find(u)] = find(v);
}

void work()
{
    long long sum = 0;
    for(int i = 1; i <= m; i ++ )
    {
        if(st[e[i].id])
        {
            sum += e[i].w;
            merge(e[i].u, e[i].v);
        }
    }
    
    for(int i = 1; i <= m; i ++ )
    {
        if(e[i].w % k) continue;
        int f1 = find(e[i].u);
        int f2 = find(e[i].v);
        if(f1 == f2) continue;
        merge(e[i].u, e[i].v);
        sum += e[i].w;
    }
    
    for(int i = 1; i <= n; i ++ )
       if(find(1) != find(i))
         return;
    
    res = min(res, sum);
}

bool check()
{
    for(int i = 1; i < k; i ++ )
       if(!chosen[i]) return false;
    
    return true;   
}

void dfs(int u)
{
    if(u == t.size())
    {
        if(check())
        {
          init();
          work();
        }  
       return;
    }
    
    st[t[u].id] = true;
    chosen[t[u].w % k] ++;
    dfs(u + 1);
    st[t[u].id] = false;
    chosen[t[u].w % k] --;
    dfs(u + 1);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        e[i].id = i;
        if(e[i].w % k != 0)
          t.push_back(e[i]);
    }
    
    sort(e + 1, e + m + 1);
    dfs(0);
    printf("%lld\n", res);
    
    return 0;
}

基础：一个%d对应一个变量

再存图的时候必须要用vector存图 不然会mle

遍历注意范围

调试信息要全部注释掉

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>
using namespace std;
string s;
int cnt1,cnt2;
bool dfs(int &now)
{
    string t="";
    vector<pair<int,int>> cnt;
    while(now<s.size())
	{
        if(s[now]=='(')
		{
            int re1=cnt1,re2=cnt2;
            t+=(char)(dfs(++now)+'0');
            cnt.push_back(make_pair(cnt1-re1,cnt2-re2));
        }
        else if(isdigit(s[now])||(s[now]=='|'||s[now]=='&'))
		{
            t+=s[now];
            cnt.push_back(make_pair(0,0));
        }
        else break;
        now++;
    }
    int r1=cnt1,r2=cnt2;
    string t1="";
    vector<pair<int,int>>vec;
    for(int i=0;i<t.size();i++)
	{
        if(t[i+1]=='&')
		{
            bool flag=0,ans=(t[i]-'0');
            int j,s1=cnt[i].first,s2=cnt[i].second;
            for(j=i+2;j<t.size()&&t[j-1]=='&';j+=2)
			{//短路 
				
                if(!ans) cnt1++,s1++,flag=1;
                if(flag) cnt1-=cnt[j].first,cnt2-=cnt[j].second;
                else s1+=cnt[j].first,s2+=cnt[j].second;
                ans&=(t[j]-'0');
            }
            vec.push_back(make_pair(s1,s2));
            t1+=(char)(ans+'0');
            i=j-2;
        }
        else vec.push_back(cnt[i]),t1+=t[i];
    }
    int ans=0,flag=0;
    for(int i=0;i<t1.size();i+=2)
	{
        if(ans)
			cnt2++,flag=1;
        if(flag)
			cnt1-=vec[i].first,cnt2-=vec[i].second;
        ans|=(t1[i]-'0');
    }
    return ans;
}
int main()
{
    cin>>s;
    int st=0;
    cout<<dfs(st)<<endl<<cnt1<<" "<<cnt2;
}

https://www.luogu.com.cn/problem/P8815

if(!ans) cnt1++,s1++,flag=1; if(flag) cnt1-=cnt[j].first,cnt2-=cnt[j].second;
顺序不能错

能放inline就尽量放inline

P1941

双数组压缩的一维dp（dp[2][11111])

存的时候是

1
dp[i%2][j]=min(dp[(i+1)%2][j-x[i]]+1,dp[i%2][j-x[i]]+1);

注意上一行是(i+1)%2

P1064

01背包数组1e6开不下

其他的用贪心做

P2015

dfs超慢

用

1
2
3
4
for(int j=m;j>=1;j--)
{
    for(int k=j-1;k>=0;k--)
    {

来做

CF607B

区间dp记得初始化为0x3f3f3f3f