The 14th Jilin Provincial Collegiate Programming Contest（补题）
A
这个题目我理解错了，题目里说的距离我以为是绝对值，没想到是差值，意思理解对了就很容易
#include <iostream>
#include <string>
#include <map>
using namespace std;
const int maxn=2e5+10;
#define da cout<<"Major triad\n"
#define xiao cout<<"Minor triad\n"
#define no cout<<"Dissonance\n"
map<string,int>val;
void init()
{
val["C"]=1;
val["C#"]=2;
val["D"]=3;
val["D#"]=4;
val["E"]=5;
val["F"]=6;
val["F#"]=7;
val["G"]=8;
val["G#"]=9;
val["A"]=10;
val["A#"]=11;
val["B"]=12;
}
void solve()
{
string a,b,c;
cin>>a>>b>>c;
int n1=val[a],n2=val[b],n3=val[c];
if (n2<n1) n2+=12;
if (n3<n2) n3+=12;
if ((n2-n1)==4&&(n3-n2)==3)
{
da;
return ;
}
if ((n2-n1)==3&&(n3-n2)==4)
{
xiao;
return ;
}
no;
return ;
}
int main ()
{
int t;
init();
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
给我们两个字符串，问我们第一个字符串有多少个子序列和第二个字符一样
这一个是一个dp
状态转移方程具体看代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define int long long
const int mod=1e9+7;
signed main ()
{
string s,ss;
while (cin>>s>>ss)
{
int n=s.size();
s=" "+s;
int m=ss.size();
ss=" "+ss;
vector<int>dp(m+10,0);
dp[1]=1;
for (int i = 1; i <=n; i++)
{
for (int j = m; j >= 1; j--) //好好体会，我也不怎么会用语言表达
{
if (s[i] == ss[j])
{
dp[j+1] = (dp[j+1] + dp[j]) % mod;
}
}
}
cout<<dp[m+1]<<'\n';
}
system ("pause");
return 0;
}
E
这个是给我们n个数，我们要尽量把这个数组的长度变小，我们可以把ai和ai+1变成ai%ai+1或者是ai+1%ai
ai,ai+1我们可以把这两个数变成min(ai,ai+1),那么我们最后留下的那些数一定是最小的那个数值
假设最小的数是mi,有cnt个
但是如果n个数都是mi的倍数，那么我们最后的答案是让mi和那些大于mi的数一定是（cnt+1)/2
如 2 2 2 4 8
2 2 2 2
0 0
最后只剩两个
如果存在一个数不是2的倍数，ans=1
2 2 2 4 8 3
2 2 2 4 3
2 2 2 3
2 2 1
2 1
1
（我们可以让保留那个不是mi倍数的数x，然后把（mi和x）变成x%mi(这个一定变成mi小的数，那这个就是最小的数了，最后一定会只剩下这个)
#include <iostream>
using namespace std;
const int maxn=1e6+10;
#define int long long
int t,n,a[maxn];
void solve()
{
cin>>n;
int mi=1e9+10;
int cnt=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]<mi)
{
mi=a[i];
cnt=1;
}
else if (a[i]==mi)
{
cnt++;
}
}
bool yes=false;
for (int i=1;i<=n;i++)
{
if (a[i]%mi)
{
yes=true;
break;
}
}
if (yes)
{
cout<<1<<'\n';
return ;
}
cout<<(cnt+1)/2<<'\n';
return ;
}
signed main ()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
G
这个题我又理解错了
这个题是给我们一个n,m，我们知道有一个nXm的矩阵，一开始是0
然后每一个i和j都会翻转一次（0变成1,1变成0）（我看了题目以为是每一个坐标（i,j),翻转(i,j)时所有行为i的倍数都会翻转，所有列为j的倍数的都会翻转，结果后来才知道根本不是每个坐标，而是i是从1到n都有一次，j是1到m都有一次）
我们只需要翻转奇数次的才会变成1，而我们需要知道最后有多少个1
判断翻转几次，需要知道总共有几个因数（而奇数个因数一定是平方数，那我们只需要判断1到n有几个平方数，1到m有几个平方数，然后两个相乘）
这个判断1到n里面有几个平方数的方法蛮好的（比我想的好）
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define int long long
int t,n,m;
int get(int x)
{
int ans=sqrt(x)-1;
ans=max(ans,0ll);
while ((ans+1)*(ans+1)<=x) ans++;
return ans;
}
void solve()
{
cin>>n>>m;
int ans=get(n)*get(m);
cout<<ans<<'\n';
return ;
}
signed main ()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
J
这个是给我们一个的3X3的棋盘，一人填X，一人填O，空格的是.
还会给我们一个数x,如果x=1是先手在这个棋盘里填O的那个人，否则是填X那个人
每个人的目标都不一样
int ans=cnt1-cnt2(cnt1是O的分数，cnt2是X的分数)
X那个人想让两人的ans更大，O那个人想要ans更小
分数时那个人在3X3的棋盘里可以连成一条（3个）的数量
最多有3的9次方中情况
我们可以用dfs遍历，不过每一种棋盘我都会转换成一个hash值，然后判断此时是求最大还是求最小
dp[t][op];//t是这一个棋盘的hash值，op=1时，这一个棋盘的时候差值最大的时候，0是差值最小的情况
//对于每一种情况，一个hash对应一个答案，所以我们只需要在最开始的时候初始化，我觉得还有点像记忆化搜索
其他的看代码
算法知识：对抗搜索
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
#define int long long
//const int inf=1e9+10;
#define inf 0x3f3f3f3f
struct state
{
char s[4][4];
int gethash()
{
int ans=0;
for (int i=1;i<=3;i++)
{
for (int j=1;j<=3;j++)
{
if (s[i][j]=='.')ans=ans*3;
else if (s[i][j]=='X') ans=ans*3+1;
else ans=ans*3+2;
}
}
return ans;
}
int calc()
{
int cnt1=0,cnt2=0;
if (s[2][2]=='O')
{
if (s[1][1]=='O'&&s[3][3]=='O') cnt1++;
if (s[1][3]=='O'&&s[3][1]=='O') cnt1++;
if (s[1][2]=='O'&&s[3][2]=='O') cnt1++;
if (s[2][1]=='O'&&s[2][3]=='O') cnt1++;
}
else
{
if (s[1][1]=='X'&&s[3][3]=='X') cnt2++;
if (s[1][3]=='X'&&s[3][1]=='X') cnt2++;
if (s[1][2]=='X'&&s[3][2]=='X') cnt2++;
if (s[2][1]=='X'&&s[2][3]=='X') cnt2++;
}
if (s[1][1]=='O')
{
if (s[1][2]=='O'&&s[1][3]=='O') cnt1++;
if (s[2][1]=='O'&&s[3][1]=='O') cnt1++;
}
else
{
if (s[1][2]=='X'&&s[1][3]=='X') cnt2++;
if (s[2][1]=='X'&&s[3][1]=='X') cnt2++;
}
if (s[3][3]=='O')
{
if (s[1][3]=='O'&&s[2][3]=='O') cnt1++;
if (s[3][1]=='O'&&s[3][2]=='O') cnt1++;
}
else
{
if (s[1][3]=='X'&&s[2][3]=='X') cnt2++;
if (s[3][1]=='X'&&s[3][2]=='X') cnt2++;
}
return cnt1-cnt2;
}
bool isend()
{
for (int i=1;i<=3;i++)
{
for (int j=1;j<=3;j++)
{
if (s[i][j]=='.') return false;
}
}
return true;
}
};
int dp[100007][2];
int dfs(state ss,int op)
{
int st=ss.gethash();
if (dp[st][op]!=-inf)
{
return dp[st][op];
}
if (ss.isend())//只有在所有的地方都填满了才可以计算，到最后一步
{
return ss.calc();
}
if (op)//填O
{
for (int i=1;i<=3;i++)
{
for (int j=1;j<=3;j++)
{
if (ss.s[i][j]=='.')
{
state nex=ss;
nex.s[i][j]='O';//改变状态
dp[st][op]=max(dp[st][op],dfs(nex,1-op));//选大的
}
}
}
}
else //填X
{
dp[st][op]=inf;
for (int i=1;i<=3;i++)
{
for (int j=1;j<=3;j++)
{
if (ss.s[i][j]=='.')
{
state nxt=ss;
nxt.s[i][j]='X';
dp[st][op]=min(dp[st][op],dfs(nxt,1-op));//选小的
}
}
}
}
return dp[st][op];
}
void solve()
{
for (int i=0;i<=100000;i++)
{
for (int j=0;j<=1;j++)
{
dp[i][j]=-inf;
}
}
int op;
cin>>op;
state st;
for (int i=1;i<=3;i++)
{
for (int j=1;j<=3;j++)
{
cin>>st.s[i][j];
}
}
int ans=dfs(st,op);
cout<<ans<<'\n';
return ;
}
signed main ()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0;i<=100000;i++)
{
for (int j=0;j<=1;j++)
{
dp[i][j]=-inf;
}
}
int t;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
M
这个是判断l到r这一段数里的所有偶数个的数异或值
根据常识，如果一段数里的数异或起来，最后剩下的是所有奇数的异或值，而题目要求我们偶数个的异或和，那我们只需要把每一个数的数量+1（我们可以先存下sum[i],1到i的前缀异或）
但是我们还需要l和r这一段的出现过的数（每个数都只有一个）
这个就需要用到树状数组
遍历的时候如果一个数之前出现过，那么就把树状数组中，在之前出现的位置减去这个数，再在新的位置加上这个数。（具体看代码，我有点不太清楚，毕竟还是第一次知道这个用处，大开眼界，(✪ω✪)）
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
#define int long long
#define lowbit(x) (x&(-x))
const int maxn=5e5+10;
int a[maxn],sum[maxn],n,q,ans[maxn];
int c[maxn];
map<int,int>mp;
struct node
{
int l,r,pos;
friend bool operator <(const node x,node y)
{
return x.r<y.r;
}
};
node Q[maxn];
void add(int x,int val)
{
while (x<=n)
{
c[x]^=val;
x+=lowbit(x);
}
return ;
}
int query(int x)
{
int res=0;
while (x)
{
res^=c[x];
x-=lowbit(x);
}
return res;
}
signed main ()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]^a[i];
}
for (int i=1;i<=q;i++)
{
cin>>Q[i].l>>Q[i].r;
Q[i].pos=i;
}
sort(Q+1,Q+1+q);
int L=1;
for (int i=1;i<=q;i++)//这个就是求l到r出现过的数的异或，下面是具体操作
{
while (L<=Q[i].r)
{
if (mp.count(a[L]))
{
add(mp[a[L]],a[L]);
}
mp[a[L]]=L;
add(L,a[L]);
L++;
}
int res = sum[Q[i].r] ^ sum[Q[i].l - 1];//这一段本来的前缀异或
int res1 = query(Q[i].r) ^ query(Q[i].l - 1);//这一段出现过的数再来一次，改变奇偶性
res ^= res1;
ans[Q[i].pos]=res;
}
for (int i=1;i<=q;i++)
{
cout<<ans[i]<<'\n';
}
system ("pause");
return 0;
}
好了，加油ヾ(◍°∇°◍)ﾉﾞ
标签：Provincial,val,Contest,int,long,ai,补题,ans,include From： https://www.cnblogs.com/righting/p/17033350.html