The 14th Jilin Provincial Collegiate Programming Contest
The 14th Jilin Provincial Collegiate Programming Contest
目录- The 14th Jilin Provincial Collegiate Programming Contest
- Problem A. Chord
- Problem B. Problem Select
- 题解
- 代码
- Problem C. String Game
- 题解
- 代码
- Problem D. Trie
- Problem E. Shorten the Array
- 题解
- 代码
- Problem F. Queue
- 题解
- 代码
- Problem G. Matrix
- 题解
- Problem H. Curious
- 题解
- Problem I. World Tree
- Problem J. Situation
- Problem K. Forager
- Problem L. Swimmer
- Problem M. Upanishad
- Problem N. Expressway
Problem A. Chord
Problem B. Problem Select
题解
签到题，sscanf从字符串中读入数字，排个序取前k个。
代码
点击查看代码
#include
#define rep(i, l, r) for (int i = l, iss = r; i <= iss; ++i)
#define per(i, l, r) for (int i = r, iss = l; i >= iss; --i)
#define pb emplace_back
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 1050;
int main()
{
int tc;
int n, m, k, t, in;
char s[N];
vector ans;
for (scanf("%d", &tc); tc; --tc)
{
scanf("%d%d", &n, &k);
rep(i, 1, n)
{
scanf("%s", s);
m = strlen(s);
rep(i, 0, m - 1) if (s[i] == '/') in = i;
sscanf(s + in + 1, "%d", &t);
ans.push_back(t);
}
sort(ans.begin(), ans.end());
rep(i, 0, k - 1) printf(i + 1 == k ? "%d\n" : "%d ", ans[i]);
ans.clear();
}
return 0;
}
/*
2
3 2
http://acm.hit.edu.cn/problemset/1003
http://acm.hit.edu.cn/problemset/1002
http://acm.hit.edu.cn/problemset/1001
4 1
http://acm.hit.edu.cn/problemset/1001
http://acm.hit.edu.cn/problemset/2001
http://acm.hit.edu.cn/problemset/3001
http://acm.hit.edu.cn/problemset/501
*/
Problem C. String Game
题解
求一个串在另一个串中作为子串的出现次数
记 a[1:n] 为母串, b[1:m] 为子串;
设 f[i][j] = k : b[1:j]在a[1:i]中作为子串 且 a[i]=b[j] 出现的次数, 有转移方程$ f[i][j]= \Sigma_{x=1}^{i-1}{f[x][j-1]}$
代码
点击查看代码
#include
#define rep(i,l,r) for(int i=l,iss=r;i<=iss;++i)
#define per(i,l,r) for(int i=r,iss=l;i>=iss;--i)
#define pb emplace_back
#define endl '\n'
typedef long long ll;
using namespace std;
const int N=5050,M=1050,P=1e9+7;
int n,m;
char a[N],b[M];
ll f[N];
int main ()
{
while(scanf("%s%s",a+1,b+1)!=EOF)
{
n=strlen(a+1),m=strlen(b+1);
rep(i,1,n)f[i]=(a[i]==b[1]?1:0);
rep(j,2,m)
{
ll prefix_sum=0;
rep(i,1,n)prefix_sum+=f[i];
per(i,1,n)
{
prefix_sum-=f[i];
if(a[i]==b[j])f[i]=prefix_sum%P;
else f[i]=0;
}
}
ll ans=0;
rep(i,1,n)ans+=f[i];
printf("%lld\n",ans%P);
}
return 0;
}
/*
eeettt
et
eeettt
te
*/
Problem D. Trie
Problem E. Shorten the Array
题解
结论题
什么情况下会是1?: \(\exist s[i],s.t.\ s[i]\ \%\ min_x{s[x]}!=0\)
其它情况: \(ans=cnt(min_x{s[x]})+1>>1\)
代码
点击查看代码
#include
#define rep(i, l, r) for (int i = l, iss = r; i <= iss; ++i)
#define per(i, l, r) for (int i = r, iss = l; i >= iss; --i)
#define pb emplace_back
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 1e6 + 500;
int n, a[N];
int main()
{
int tc, ele, cnt;
bool flag;
for (scanf("%d", &tc); tc; --tc)
{
scanf("%d", &n);
rep(i, 1, n) scanf("%d", a + i);
ele = a[1], flag = false;
rep(i, 1, n) if (a[i] < ele) ele = a[i];
rep(i, 1, n) if (a[i] % ele != 0)
{
flag = true;
break;
}
if (flag)
{
printf("1\n");
}
else
{
cnt = 0;
rep(i, 1, n) if (a[i] == ele) cnt++;
printf("%d\n", cnt + 1 >> 1);
}
}
return 0;
}
Problem F. Queue
题解
可以是一道较难的题目, 动态逆序对可持久化线段树可做, 出题人仁慈地放过了暴力;
考察交换两个数字对逆序对数量的贡献, 仅有 \(p_1
代码
点击查看代码
#include
#define rep(i, l, r) for (int i = l, iss = r; i <= iss; ++i)
#define per(i, l, r) for (int i = r, iss = l; i >= iss; --i)
#define pb emplace_back
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 1e5 + 500;
int n, s[N], m;
ll ori, ans;
struct BIT
{
#define Low_Bit(x) (x & (-x))
private:
int ran, bit[N];
public:
BIT(int ran) : ran(ran)
{
memset(bit, 0, sizeof(bit));
}
void add(int p, int x)
{
for (; p <= ran; p += Low_Bit(p))
bit[p] += x;
}
int sum(int p)
{
int rec = 0;
for (; p > 0; p -= Low_Bit(p))
rec += bit[p];
return rec;
}
#undef Low_Bit
};
void Init();
void Get_inversions();
void Process();
int main()
{
int tc;
for (scanf("%d", &tc); tc; --tc)
{
Init();
Get_inversions();
Process();
printf("%lld\n", ans);
}
return 0;
}
void Process()
{
scanf("%d", &m);
int l, r,f,lv,rv, cnt;
rep(i,1,m)
{
scanf("%d%d", &l, &r);
if (s[l] == s[r])
continue;
cnt = 1;
if (s[l] < s[r])f=1,lv=s[l],rv=s[r];
else f=-1,lv=s[r],rv=s[l];
rep(j,l+1,r-1)
{
if (s[j] >= lv && s[j] <= rv)cnt++;
if (s[j] > lv && s[j] < rv)cnt++;
}
ori=ori+f*cnt;
if(ori max_s) max_s = s[i];
BIT *bit = new BIT(max_s);
per(i, 1, n)
{
ori += bit->sum(s[i] - 1);
bit->add(s[i], 1);
}
ans = ori;
delete bit;
}
Problem G. Matrix
题解
当横纵坐标的乘积为奇数时, $ a(i,j)=1 $ ;
即横纵坐标值应分别为奇数;
$ans= \left\lfloor \sqrt{n} \right\rfloor* \left\lfloor \sqrt{m} \right\rfloor $
Problem H. Curious
题解
莫比乌斯反演 unfinished