2019CSP-S模拟赛
于2020/4,2020/7/24两测
作为疫情期间学习过的证据
T1
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
long long T;
int xx[5010], yy[5010], xt, yt;
long long ansx, ansy;
string s;
int main(){
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
cin >> s;
// cout << s << endl;
// scanf("%s",s+1);
for(int i = 1; i <= s.size(); i++){
if(s[i-1] == 'E'){
xx[i] = xx[i - 1] + 1;
yy[i] = yy[i - 1];
}
else if(s[i-1] == 'W'){
xx[i] = xx[i - 1] - 1;
yy[i] = yy[i - 1];
}
else if(s[i-1] == 'N'){
yy[i] = yy[i - 1] + 1;
xx[i] = xx[i - 1];
}
else if(s[i-1] == 'S'){
yy[i] = yy[i - 1] - 1;
xx[i] = xx[i - 1];
}
// cout << xx[i] << " " << yy[i] << endl;
}
cin >> T;
xt = xx[s.size()];
yt = yy[s.size()];
ansx += T / s.size() * xt;
ansy += T / s.size() * yt;
ansx += xx[T % s.size()];
ansy += yy[T % s.size()];
printf("%lld %lld
", ansx, ansy);
return 0;
}
T2
矩阵快速幂
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#define ll long long
#define MOD 1000000007
using namespace std;
int t;
ll n;
struct mat{
ll m[4][4];
mat(){
memset(m, 0, sizeof(m));
}
void base(){
m[1][3] = 1;
m[2][1] = 1;
m[3][2] = 1;
m[3][3] = 1;
}
void pre(){
m[1][1] = 1;
m[2][2] = 1;
m[3][3] = 1;
}
};
mat operator *(mat a, mat b){
mat res;
for(int i = 1; i <= 3; i++){
for(int j = 1; j <= 3; j++){
for(int k = 1; k <= 3; k++){
res.m[i][j] += a.m[i][k] * b.m[k][j];
res.m[i][j] %= MOD;
}
}
}
return res;
}
/*
void print(mat a){
for(int i = 1; i <= 3; i++){
for(int j = 1; j <= 3; j++) cout << a.m[i][j] << " ";
cout << endl;
}
}
*/
mat ksm(ll num){
mat ans, a;
ans.pre();
a.base();
while(num){
if(num & 1){
ans = ans * a;
}
num >>= 1;
a = a * a;
/* print(ans);
printf("
");
print(a);
printf("
");
*/ }
return ans;
}
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
if(n <= 3){
printf("1
");
}
else{
mat ans = ksm(n - 3);
// print(ans);
ll Ans = 0;
Ans += ans.m[1][3];
Ans %= MOD;
Ans += ans.m[2][3];
Ans %= MOD;
Ans += ans.m[3][3];
Ans %= MOD;
printf("%lld
", Ans);
}
}
return 0;
}
T3
对n个点分别建黑白两点。
停留1秒转化为从一种颜色的点走到本点的另一颜色的点。
跑最短路即可。
注意迷惑的题目描述。
u->v是从一秒前的u到一秒后的v，但是影响k值的颜色状态全部取一秒之前。
停留，停留一秒后的颜色决定是否加s[i]。
做题历程：
3个月前第一次做：这什么玩意
3个月前听WZ讲：WOW，强！妙！
3个月前听完后自己写：
根据题意建图，跑一遍spfa完事
搞成2n个点，前n个白，后n个黑
对于u,v,k
颜色一样，add(u,v,k);add(u+n,v+n,k);
颜色不一样， add(u,v+n,k-);add(u+n,v,k+)
处理完后，自己的黑白两点相连
add(i,i+n,s[i]);add(i+n,i,0);
spfa(1)
spfa(1+n)
ans=min(dist[n],dist[n*2])
我的程序怎么了呜呜呜调不出来
OH,好，我发现当年真是没有完全懂，程序写的也不对。
3个月后，80pts。
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 5010, maxm = 30010;
struct Edge{
int to, nxt;
ll k;
}ed[maxm * 2 + maxn * 2];
int n, m, first[maxn * 2], en, u, v;
ll k, w[maxn], s[maxn];
bool col[maxn * 2];
inline int read(){
int res = 0;
char c = getchar();
while(c < '0' || c > '9'){
c = getchar();
}
while(c <= '9' && c >= '0'){
res *= 10;
res += c - '0';
c = getchar();
}
return res;
}
inline ll llread(){
ll res = 0;
char c = getchar();
while(c < '0' || c > '9'){
c = getchar();
}
while(c <= '9' && c >= '0'){
res *= 10;
res += c - '0';
c = getchar();
}
return res;
}
void add(int u, int v, ll k){
ed[++en].to = v;
ed[en].k = k;
ed[en].nxt = first[u];
first[u] = en;
}
ll dist[maxn * 2];
bool inque[maxn * 2];
priority_queue <pair <int, int> > q;
void dijkstra(int s){
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
inque[s] = 1;
q.push(make_pair(0,s));
while(q.size()){
int u = q.top().second;
q.pop();
for(int e = first[u]; e; e = ed[e].nxt){
int v = ed[e].to;
if(dist[v] > dist[u] + ed[e].k){
dist[v] = dist[u] + ed[e].k;
if(!inque[v]){
q.push(make_pair(-dist[v], v));
}
}
}
}
}
//完成后2mins,只看
int main(){
freopen("holes.in","r",stdin);
freopen("holes.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
col[i] = read();
col[i + n] = !col[i];
}
// for(int i = 1; i <= n + n; i++) cout << col[i] << " ";
// cout << endl;
for(int i = 1; i <= n; i++){
w[i] = llread();
}
for(int i = 1; i <= n; i++){
s[i] = llread();
if(col[i] == 0)//白洞
{
add(i, i + n, s[i]);
add(i + n, i, 0);
}
else {
add(i, i + n, 0);
add(i + n, i, s[i]);
}
}
for(int i = 1; i <= m; i++){
u = read(); v = read();
k = llread();
// scanf("%lld",&k);
if(col[u] == 0 && col[v] == 0)//w->b w-w
{
add(u, v + n, k);
add(u + n, v, k);
// add(u, v + n, (k - abs(w[u] - w[v]) )>= 0 ? (k - abs(w[u] - w[v]) ): 0);
// add(u + n, v, k + abs(w[u] - w[v]));
}
else if(col[u] == 0 && col[v] == 1)//w->w w-b
{
add(u, v + n, (k - abs(w[u] - w[v]) )>= 0 ? (k - abs(w[u] - w[v]) ): 0);
add(u + n, v, k + abs(w[u] - w[v]));
// add(u, v + n, k);
// add(u + n, v, k);
}
else if(col[u] == 1 && col[v] == 0)//b->b b-w
{
add(u, v + n, k + abs(w[u] - w[v]));
add(u + n, v, (k - abs(w[u] - w[v]) )>= 0 ? (k - abs(w[u] - w[v]) ): 0);
// add(u, v + n, k);
// add(u + n, v, k);
}
else if(col[u] == 1 && col[v] == 1)//b->w b-b
{
add(u, v + n, k);
add(u + n, v, k);
// add(u, v + n, k + abs(w[u] - w[v]));
// add(u + n, v, (k - abs(w[u] - w[v]) )>= 0 ? (k - abs(w[u] - w[v]) ): 0);
}
}
dijkstra(1);
ll ans;
if(dist[n] < dist[n + n]) ans = dist[n];
else ans = dist[n + n];
printf("%lld
",ans);
return 0;
}
"%lld"！！！！！！！