12.11 刷题
《算法竞赛》这本书看了很多了，但是题目没咋做，所以今天来刷一下题
P1996约瑟夫问题
还依稀记得大一的时候被约瑟夫支配的恐惧（哭），但是现在做就感觉很简单（虽然也敲了一会，今早感觉状态不是很好）
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll p[105];
ll n, m;
int main()
{
cin >> n >> m;
ll cnt = 0, index_now = 0, sum = 0;
while (cnt < m && sum != n)
{
if (!p[index_now])
{
cnt++;
if (cnt == m)
{
p[index_now] = 1;
cout << index_now + 1 << ' ';
cnt = 0;
sum++;
}
}
index_now = (index_now + 1) % n;
}
return 0;
}
P1540 机器翻译
这题首先肯定是要用到队列的，数据量也不大，本来是想用n2的复杂度直接莽的，但是后面发现通过哈希其实是可以把时间复杂度降到On的，代码如下：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll m,n;
ll hashh[1005];
queue<ll> q;
int main()
{
cin>>m>>n;
ll cnt=0,ans=0;//cnt是为了记录队列有没有满，ans是记录查阅次数
for(int i=0;i<n;i++)
{
ll word;
cin>>word;
if(hashh[word]==0)
{
if(cnt!=m)
{
cnt++;
}
else
{
ll tp=q.front();
q.pop();
hashh[tp]=0;
}
q.push(word);
hashh[word]=1;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
P1886 滑动窗口
这题以前做过，之前肯定是看模版写的单调队列（就是检查到a[i]时，让a[i]成为队列中最大的元素，来维持队列的单调性），今天我瞄了一眼发现这题完全可以用优先队列去写，因为数据量并不是很大，只有106,所以nlogn也是可以过的。
但是单调队列的时间复杂度显然要更优越，是On，所以如果数据量有109，优先队列估计也过不了
优先队列代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k;
struct node
{
ll index;
ll value;
};
node a[1000005];
struct compare
{
bool operator()(const node &p1, const node &p2)
{
if (p1.value < p2.value)
return true;
if (p1.value == p2.value)
return p1.index < p2.index;
return false;
}
};
struct compare2
{
bool operator()(const node &p1, const node &p2)
{
if (p1.value > p2.value)
return true;
if (p1.value == p2.value)
return p1.index > p2.index;
return false;
}
};
priority_queue<node, vector<node>, compare2> q1;
priority_queue<node, vector<node>, compare> q2;
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i].value;
a[i].index = i;
}
for (int i = 1; i <= n; i++)
{
q1.push(a[i]);
if (i >= k)
{
while (q1.top().index < i - k + 1)
q1.pop();
cout << q1.top().value << ' ';
}
}
cout << endl;
for (int i = 1; i <= n; i++)
{
q2.push(a[i]);
if (i >= k)
{
while (q2.top().index < i - k + 1)
q2.pop();
cout << q2.top().value << ' ';
}
}
return 0;
}
单调队列代码：(感觉十分简洁优雅，而且队列里面只存序号这点很高明，如果是我我就定义结构体了)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k;
deque<ll> q;
ll a[1000005];
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (!q.empty() && q.front() < i - k + 1)
q.pop_front();
while (!q.empty() && a[q.back()] > a[i])
q.pop_back();
q.push_back(i);
if (i >= k)
cout << a[q.front()] << ' ';
}
cout << endl;
while (!q.empty())
q.pop_back();
for (int i = 1; i <= n; i++)
{
while (!q.empty() && q.front() < i - k + 1)
q.pop_front();
while (!q.empty() && a[q.back()] < a[i])
q.pop_back();
q.push_back(i);
if (i >= k)
cout << a[q.front()] << ' ';
// cout << "i" << i << endl;
// for (auto it : q)
// cout << a[it] << ' ';
// cout << endl;
}
return 0;
}
两日总结：
写快一点吧
这三题都是12.11号刷的 今天没抽出时间刷题
昨天去找两位姐姐吃了个饭 玩的挺开心的
然后今天跟学长也出去吃了个饭 吃了日料之后又去吃川菜 笑死我了 花了310左右
撑死了
然后就是最近想法比较多 也跟子雄说了 子雄的执行力是真的强 跟他说他真的就去立马做了
最近喜欢看《马斯克传》 写的很幽默 找到新的精神支撑了
手语社那个圈子总感觉怪怪的 是我想多了么
送给自己5个字：
偏执而疯狂
去看书了